글의 주제와 상관은 없지만 프로그래밍을 잘하기 위한 필요한 능력 중에 하나가 단기기억력이라고 생각된다. 수천, 수만 줄의 코드에서 연관된 코드들을 살펴볼 때 단기 기억력이 좋다면 까먹고 다시 돌아가는 일이 적어지기 때문이다. 단기 기억력은 결국은 집중력과 연관되는데 아무튼 프로그래머는 참 에너지 소비가 많은 직종 중에 하나라고 생각된다.
그럼 이 글의 주제인 재귀함수는 무엇인가?
쉽게 말해 자기 자신을 호출하는 함수를 말한다. 혹시 마트로시카라는 러시아 인형을 본적이 있는가?
인형을 열어보면 그 안에 자신과 똑같은 인형이 들어있다. 안에 들어 있는 인형을 열어봐도 또 그 안에 똑같은 인형이 들어있고 이렇게 반복된다.
재귀함수도 비슷하다. 예를들어 abc라는 함수가 있는데 이 함수는 자기 자신인 abc 함수를 호출하는 코드를 가지고 있다. 이 때 abc함수를 한번 호출해보면 계속 반복해서 abc를 호출되게 된다.이런 반복적인 호출은 특별한 조치를 취하지 않으면 무한반복 된다. 다음은 무한반복되는 재귀 함수의 예제 코드다.
함수 abc는 "recursion"이라는 단어를 출력하는 기능을 가진 함수다. 그리고 내부에서 자기 자신을 호출하는 재귀 함수다. 이 함수의 호출 결과 "recusion"이 무한반복 호출되다가 결국 Stack overflow 에러가 발생한다.
스택(stack)의 크기는 유한한데 프로그램에서 함수를 호출하면 호출된 함수의 정보(주소, 인자 등..)가 스택에 쌓인다. 이렇게 스택에 쌓이는 함수의 정보는 함수가 리턴(return)되기 전 까지 스택(stack)영역을 차지한다.
따라서 재귀 함수처럼 함수가 리턴(return)되기 전에 함수를 호출하는 패턴이 무한 반복되면 결국 스택(stack)영역이 꽉 차게 되어 Stack overflow(스택 오버플로)가 발생하는 것이다.
그러면 재귀 함수를 어떻게 사용해야 하는가?
for 문을 사용할 때 무한루프에 빠지지 않도록 for문 내에서 for문을 탈출하기 위한 조건을 정해준다.
재귀 함수 역시 마찬가지다. 자기 자신을 호출하는 패턴을 끝내기 위한 탈출 조건을 만들어야 하는데 이를 기저 조건(base case)라고 한다.
다음은 1부터 n까지 더하는 재귀함수를 보여준다.
Base case
if (n < 1) return 0;
sum 함수의 정의에서 n이 1보다 작아질 때가 기저조건(base case)가 된다. n의 값이 0이 되면 함수는 0을 반환하며 종료되며 재귀 함수는 회귀를 한다. 아래 그림 참고.
(n이 1이상인 경우 recursive case라고 할 수 있다.)
sum함수는 인수로 받은 값 n까지의 합을 구하는 함수다. 재귀는 수학적 귀납법으로 증명할 수 있다. 결론은 다음과 같다.
n까지의 합은 n-1까지의 합에 n을 더한 것과 같다.
sum(10)을 호출하면 자신의 코드가 반환되기도 전에 sum(9)를 호출한다. sum(9)역시 sum(8)을 호출하고 이렇게 해서 sum(0)까지 호출하면 기저 조건에 의해서 sum(0)은 0을 반환한다. sum(0)이 값을 반환했으므로 sum(0)을 호출한 sum(1)은 나머지 코드인 return 1+ sum(0)를 실행한다. (sum(0)은 0을 반환했으므로 return 1+0을 실행한다.)
같은 방식으로 sum(2)의 나머지 코드가 실행되어 return 2+1+0이 실행되고 이렇게 해서 처음에 호출한 함수 sum(10)까지 회귀하여 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1을 반환한다.(1 부터 10까지의 합)
이와 유사한 방식으로 1 부터 n까지의 곱(n!)을 구하거나 피보나치 수열 또는 점화식과 같은 수식을 재귀함수로 나타낼 수 있다.
재귀 함수는 스택을 지속적으로 사용하므로 n의 값이 커질 수록 함수의 호출 깊이가 깊어져 메모리를 비정상적으로 많이 사용하거나 앞에서 본 것 처럼 스택 오버플로(stack overflow)를 발생시킬 수 있다. 컴퓨터의 사양에 따라서 가능한 호출 깊이의 차이가 있으므로 범용적인 프로그램에서는 재귀함수가 독이될 수가 있다.
하지만 재귀함수는 점화식과 같이 대단히 복잡해 보이는 문제를 직관적으로 풀 수 있다. (물론 처음에는 재귀함수가 어렵게 느낄 수 있지만...)
알고리즘에서도 재귀를 사용하여 아주 간단히 풀 수 있는 문제들이 많이 있다. 여러 단점이 있음에도 재귀를 사용하는 이유가 있는 것이다.