재귀 호출
재귀 호출(recursive call)
재귀 호출(recursive call)이란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 것을 말합니다.
이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복될 것입니다.
따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.
프로그래밍을 처음 접하는 사람들은 이러한 재귀 호출이 왜 필요한가에 대해 이해하기 힘들 수도 있습니다.
하지만 재귀 호출은 알고리즘이나 자료 구조론에서는 매우 중요한 개념 중 하나입니다.
또한, 재귀 호출을 사용하면 복잡한 문제도 매우 간단하게 논리적으로 접근하여 표현할 수 있습니다.
재귀 호출의 개념
재귀 호출의 개념을 파악하기 위해서 우선 재귀 호출을 사용하지 않고 1부터 n까지의 합을 구하는 함수를 만들어 봅시다.
예제
int Sum(int n)
{
int result = 0;
for (int i = 1; i <= n; i++)
{
result += i;
}
return result;
}
위의 예제에서 Sum() 함수는 재귀 호출을 사용하지 않고 만든 함수입니다.
이러한 함수는 그냥 봐서는 그 목적을 바로 알 수 없으며, 코드를 해석해야 무슨 목적으로 만든 함수인지 알 수 있습니다.
즉 변수 i와 result는 왜 정의됐으며, for 문은 왜 사용되었는지 바로 알 수가 없습니다.
이제 재귀 호출을 사용하여 1부터 n까지의 합을 구하는 RecursiveSum() 함수를 만들어 봅시다.
우선 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이 아니면, n과 1부터 (n-1)까지의 합을 더한 값을 반환함.
2. n이 1이면, 그냥 1을 반환함.
끝
위와 같이 논리적인 재귀 알고리즘을 구상하고, 의사 코드를 작성하면, 재귀 호출을 이용해 바로 코드로 옮길 수 있습니다.
예제
int RecursiveSum(int n)
{
if (n == 1) // n이 1이면, 그냥 1을 반환함.
{
return 1;
}
return n + RecursiveSum(n-1); // n이 1이 아니면, n을 1부터 (n-1)까지의 합과 더한 값을 반환함.
}
실행 결과
1부터 10까지의 합은 55입니다.
위의 예제에서 만약 if 문이 없다면, 이 메소드의 재귀 호출은 무한히 반복될 것입니다.
이처럼 재귀 호출이 무한히 반복되면, 해당 프로그램은 실행 직후 스택 오버플로우(stack overflow)에 의해 종료될 것입니다.
따라서 if 문처럼 재귀 호출을 중단하기 위한 조건문을 반드시 포함해야 합니다.
이처럼 재귀 호출은 다양한 알고리즘을 표현한 의사 코드를 그대로 코드로 옮길 수 있게 해주므로, 직관적인 프로그래밍을 하는 데 많은 도움을 줍니다.
