재귀 호출
재귀 호출(recursive call)
함수란 하나의 작업을 수행하기 위해 독립적으로 설계된 프로그램 코드의 집합입니다.
C 프로그램은 이러한 함수들로 구성되며, 포함된 함수들을 사용하여 프로그램의 목적을 달성하게 됩니다.
재귀 호출(recursive call)이란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위를 의미합니다.
이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되게 됩니다.
따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.
프로그래밍을 처음 접하는 사람들은 이러한 재귀 호출이 왜 필요한가에 대해 이해하기 힘들 수도 있습니다.
하지만 재귀 호출은 알고리즘이나 자료 구조론에서는 매우 중요한 개념 중 하나입니다.
또한, 재귀 호출을 사용하면 복잡한 문제도 매우 간단하게 논리적으로 접근하여 표현할 수 있습니다.
재귀 호출의 개념
재귀 호출의 개념을 파악하기 위해서 우선 재귀 호출을 사용하지 않고 1부터 n까지의 합을 구하는 함수를 만들어 봅시다.
예제
int sum(int n) {
int i;
int result = 0;
for (i = 1; i <= n; i++)
{
result += i;
}
return result;
}
위의 예제에서 sum() 함수는 재귀 호출을 사용하지 않고 만든 함수입니다.
이러한 함수는 그냥 봐서는 그 목적을 바로 알 수 없으며, 코드를 해석해야 무슨 목적으로 만든 함수인지 알 수 있습니다.
즉 변수 i와 result는 왜 정의됐으며, for 문은 왜 사용되었는지 바로 알 수가 없습니다.
이제부터 재귀 호출을 사용하여 1부터 n까지의 합을 구하는 rSum() 함수를 만들어 봅시다.
우선 1부터 4까지의 합을 구하는 알고리즘은 다음과 같습니다.
1. 1부터 4까지의 합은 1부터 3까지의 합에 4를 더하면 됩니다.
2. 1부터 3까지의 합은 1부터 2까지의 합에 3을 더하면 됩니다.
3. 1부터 2까지의 합은 1부터 1까지의 합에 2를 더하면 됩니다.
4. 1부터 1까지의 합은 그냥 1입니다.
위와 같이 논리적인 재귀 알고리즘을 구상하고 나면, 그것을 토대로 의사 코드를 작성할 수 있습니다.
위의 알고리즘을 의사 코드(pseudo code)로 작성하면 다음과 같습니다.
의사 코드
시작
1. n이 1이 아니면, 1부터 (n-1)까지의 합에 n을 더한 값을 반환함.
2. n이 1이면, 그냥 1을 반환함.
끝
이렇게 작성된 의사 코드는 재귀 호출을 이용해 다음 예제와 같이 바로 구현할 수 있게 됩니다.
예제
int rSum(int n)
{
if (n == 1) // n이 1이면, 그냥 1을 반환함.
{
return 1;
}
return n + rSum(n-1); // n이 1이 아니면, n을 1부터 (n-1)까지의 합과 더한 값을 반환함.
}
실행 결과
1부터 5까지의 합은 15입니다.
위의 예제에서 if 문이 존재하지 않으면, 이 프로그램은 실행 직후 스택 오버플로우(stack overflow)에 의해 종료될 것입니다.
따라서 if 문처럼 재귀 호출을 중단하기 위한 조건문을 반드시 포함해야 합니다.
스택에 대한 더 자세한 사항은 C언어 스택 프레임 수업에서 확인할 수 있습니다.
이처럼 재귀 호출은 다양한 알고리즘을 표현한 의사 코드를 그대로 코드로 옮길 수 있게 해줍니다.
따라서 재귀 호출은 직관적인 프로그래밍을 하는 데 많은 도움을 줍니다.
하지만 이러한 재귀 호출은 비재귀 호출보다 실행 시간이 오래 걸리는 단점을 가지고 있습니다.
재귀호출의 단점 : 무한 재귀호출의 위험성, 성능 상의 문제
