재귀에 대하여 : 팩토리얼 알고리즘

재귀 알고리즘은 엑셀 VBA 매크로를 할때 내가 상당히 자주 쓰던 비.효.율.적. 인 방식이다.

그땐 재귀인 것을 모른 채 그냥 탱크로 밀어붙이듯이 그렇게 알고리즘을 짜서 분석을 했었다.

예를들면 이런식이다.

A1의 값을 찾아서 모든 셀을 뒤져서 해당 값을 복사해 붙여넣고
다시 A2의 값을 찾아서 모든 셀을 뒤져서 해당 값을 복사해서 붙여넣고...


이렇게 백만행 이상의 레코드를 매크로로 돌리다보면
하루 종일 컴퓨터가 돌아가게된다.

그런데도 사람이 몇십년에 걸쳐서 해야할 일을 컴퓨터가 하루만에 해주는 것에 감탄하면서
그렇게 재귀 알고리즘을 사용했었다.


재귀란 무엇일까?
재귀를 가장 알기쉽게 이해할 수 있는 알고리즘은 바로 '팩토리얼' 이다.

아래의 함수를 한번 보자

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

n=1일땐 1!이 1이므로 바로 1이 리턴되지만
n이 1보다 클땐 factorial 함수가 꼬리에 꼬리를 물면서 이어진다.

예를들어서 n=4일때
factorial(4) = 4* factorial(3) = 4*3* factirial(2) = 4*3*2* factorial(1) = 4*3*2*1 = 24

이렇게 되는 방식이다

이것이 바로 재귀함수의 모든것이다.
한 함수 안에서 동일한 함수가 꼬리에 꼬리를 물면서 이어지는 것..
마치 고대 그리스 신화에 나오는 우로보로스 처럼 말이다.

구체적인 함수 흐름은 다음과 같다.
주소를 기억하면서 꼬리에 꼬리를 물면서 이어지던 재귀함수는
최종 리턴값을 맞이하면서 다시 강을 거슬러 올라가는 연어처럼 원래의 주소로 돌아온다.

(출처 : https://treeroad.tistory.com/entry/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98)

재귀함수는 가장 단순한 방법이면서 가장 무식한 방법이다.
이는 Stack을 무한정 쌓을수도 있고,
이는 곧 심각한 Stack Overflow를 발생시킬 수 있다는 것을 의미하기 때문이다.

때문에 이러한 Stack의 문제에서 벗어나는 방법을 연구하지 않을 수 없다.
이는 '꼬리 재귀'라는 개념으로 해결할 수 있는데
이어지는 내용에서 꼬리 재귀를 살펴보도록 하겠다.