재귀 함수 & 재귀적 함수호출(recursive function call)

C언어든 C++을 공부하는 사람이라면 재귀 함수라는 용어 한 번정도는 들어봤을 것입니다.

재귀적 호출은 함수가 자기 자신을 호출하는 호출 방식입니다.

MIT 컴퓨터 프로그래밍 입문 교재인 SICP에는  재귀적 호출을 다음과 같이 이해하게 합니다.

1. Wishful Thinking('내가 하려는 작업이 이미 있다.'  라고 생각)

2. 문제를 작게 자른다.

3. 더 이상 자를 수 없는 부분(base)만 처리

재귀적 함수 호출을 이해하기 충분한 문장이라고 생각합니다.

(프로그래밍에 대한 기본 개념을 익히는 데는 참 좋은 책인 거 같습니다.)

그럼 더 자세히 알아보도록 하겠습니다.

재귀 함수를 이해하는 데 가장 좋은 예는 역시 Factorial을 구하는 문제가 아닌가 싶습니다.

Factorial이 널리 쓰이는 이유는 간단한 연산법에

재귀적 호출 이해 2, 3번째를 모두 만족하기 때문입니다.

Factorial이 무엇인지 모르는 사람은 아마 없을 것이지만, Factorial은 다음과 같은 연산입니다.

보통 누승이라고 불리는 연산이죠.

5! = 5 * 4 * 3 * 2 * 1

n! = n * (n-1) * (n-2) … 1

그럼 이 Factorial이 어떻게 2번과 3번을 만족하는 지 보도록 하겠습니다.

5!은 다음과 같이 표현됩니다.

5! = 5 * 4!

같은 방법으로 계속 이런 식으로 표현이 됩니다.

5! = 5 * (4 * 3!) ,     5! = 5 * (4 * (3 * 2!)

문제가 더 작은 문제로 반복되고 있다는 것을 알아 차리셨나요?

3번째 조건을 만족하는 것은 Factorial의 정의에 기반합니다.

'Factorial 0과 Factorial 1은 1이다' 라는 정의를 많이 들어보셨을 겁니다.

C언어에서 Factorial함수를 재귀적으로 어떻게 구현하는 지 보도록 하겠습니다.

#include <iostream>
using namespace std;

int factorial(int n)
{
	if (1 >= n)
	{
		return 1;
	}
	else
	{
		return n * factorial(n - 1);
	}
}

void main()
{
	int nRes = factorial(5);
	cout << "Result : " << nRes << endl;
}

아주 일반적인 재귀 함수 구성인데 이것이 어떻게 돌아가는 지 보도록 하겠습니다.

main 함수에서 factorial(5)로 함수를 호출했기 때문에 흐름이 factorial 함수로 넘어가겠죠.

함수가 호출되면 스택에 각종 정보(이전 스택프레임, 리턴 주소, 전달 받은 인자, 지역변수)가

저장되는데 이것을 스택 프레임이라고 합니다.

우리가 함수를 호출하면 리턴값이 어디로 전달될까요?

그렇습니다! 리턴값은 함수를 호출한 곳에 전달해주게 됩니다.(callee와 caller의 관계)

일단 factorial(5)가 실행되면 처음 if (1 >= n) 에서 체크를 하는데 false죠.

그래서 else를 실행할 것인데 else문의 내부를  주의깊게 보도록 하겠습니다.

바로 return이 될 것이라고 생각하시나요?

물론 그렇지 않습니다.

n * factorial(n-1)을 계산하고 나서 return을 할 것이기 때문입니다.

근데, factorial(n-1)또한 하나의 함수입니다.

다시 흐름이 factorial(n-1), 즉, factorial(4)가 호출되는 것입니다.

같은 방법으로 factorial(4)내부에서는 factorial(3)을 호출하게 됩니다.

이런 식으로 늘어나면서 return을 미루는 것입니다.

쭉 가다가 factorial(1)을 호출하면 이제 역으로 리턴이 시작됩니다.

왜냐하면 factorial 함수의 if문에 1이 들어오면 1을 리턴하는 것으로 되있기 때문입니다.

이 base case 때문에 재귀 함수는 무한 루프에 빠지지 않는 것입니다.

이것이 처음에 말했던 3번 조건이죠.

factorial(1)이 1을 factorial(1) 자신을 호출했던 factorial(2)에 리턴을 해줍니다.

리턴이 시작되는 거죠.

그럼 factorial(2)도 return이 미뤄졌었는데 이제 factorial(3)에 리턴이 이루어지게 됩니다.

리턴할 때 2에 전달받은 리턴값 1을 곱해서

자신을 호출했던 factorial(3)에 2를 전달해주는 것입니다.

이런 식으로 리턴이 미뤄졌다가 역으로 돌면서 값을 처리하면서 리턴하는 것입니다.

그림으로 간략하게 보면 다음과 같습니다.

재귀 함수 호출은 생각해보면 같은 함수를 호출하지만

서로 다른 함수를 호출한다고 생각하면 이해하기가 쉬울지도 모르겠습니다.

즉, factorial_5(5)는 factorial_4(4)가 주는 4! 값을 받아서 5만 곱해주는 것이고

factorial_4(4)또한 factorial_3(3)이 리턴해주는 3! 값을 받는다는 것입니다.

실제로 함수가 호출될 때 recursive하게 호출되더라도 메모리 상에 새로운 스택프레임이 생성됩니다.

하지만 recursive function call은 일반적으로 비효율적입니다.

factorial을 보통 저렇게 하는 것보다는 for문으로 돌리는 것이 훨씬 효율적인 프로그래밍이 가능합니다.

스택프레임을 새로 생성해야되고, 함수가 돌아올 때 스택프레임을 원래로 돌려야 하기 때문이죠.

하지만 이런 재귀 호출 방식을 사용해야 더 유용한 경우가 있기 때문에 사용되는 거겠죠.

그렇기 때문에 우리는 재귀 호출 방식을 배우는 것입니다.

트리나 그래프 등을 처리할 때는 재귀 호출 방식으로 구현하는 것이 훨씬 구현하기가 쉽습니다.

트리가 왜 재귀적 호출 방식에 적합한 지 보도록 하겠습니다.

트리의 노드를 지우면 다시 트리가 다시 나타납니다.

이러한 특성이 있기 때문에 재귀적 표현으로 구현하는 것이 더 용이한 것입니다.

물론 재귀가 비효율적인 경우도 존재합니다.

대표적인 예가 피보나치 수열(Fibonacci sequence)입니다.

피보나치 수열을 재귀적 형태로 작성하면 크지 않은 숫자에도 구하는 것이 거의 불가능해집니다.

피보나치 수열의 모든 경우를 탐색하기 때문입니다.

재귀적 호출의 다른 큰 단점은 스택 오버 플로우 에러가 발생할 가능성이 존재한다는 것입니다.

함수가 호출될 때마다 스택에 계속 커지는데 재귀적 호출이 지나치게 많이 반복되면

스택이 임계점까지 커지기 때문입니다.

이러한 단점이 있음에도 불구하고 재귀적 함수 호출 방식은 유연하게 코드를 작성하게 도와줍니다.