재귀(recursion)함수는 함수가 작동을 할 때 자기자신을 호출하는 함수입니다. 이런 성질때문에 반복하고자 하는 작업을 간단한 코딩으로 제법 있어보이게 할 수 있게 해주는 함수이죠.
(반복문보다 있어보이는 건 나만의 생각일까?) 사실 문제해결전략 시리즈에서 제일 첫번째 글인 반복전략을 재귀로 하는 것과 다르지 않습니다. 반복문으로 할 수 있는건 재귀함수로도 할 수 있고 재귀함수로 할 수 있는건 반복문으로도 가능합니다. 둘의 본질은 반복으로 같기 때문입니다.
예시를 하나 들어보겠습니다.
숫자 n을 입력하면 n번째 피보나치 수를 return하는 함수를 만들어봅시다. (피보나치 수가 무엇인지는 알고 있다고 가정할게요.) 결국 똑같은 반복작업이니 반복전략을 쓰면되겠죠?
반복할 절차는 다음과 같습니다.
1. 함수에 입력받은 숫자 n을 입력 받았을 때 함수(n-1)+함수(n-2)를 호출하여 return 합니다.
탈출조건은 다음과 같습니다.
1. 만약 입력받은 n이 2이면 1을 , n이 1이면 0을 return 하고 더이상의 재귀함수호출은 일어나지 않습니다.
이것을 javascript로 코딩하면 다음과 같습니다.
function fibonacci (n) {
if(n===2){
return 1;
}
if(n===1){
return 0;
}
return fibonacci(n-1)+fibonacci(n-2);
}반복전략으로 이 것을 재현하려고 했다면 변수 두개를 이용해 1번째 fibonacci와 0번째 fibonacci를 할당해 차례차례 1번째,2번째에서부터 3번째,4번째,5번째를 구해가는 전략을 써야했을 것입니다. 즉 반복전략과는 탑다운이냐 바텀업이냐라는 차이가 있습니다.
그렇다면 이러한 재귀함수를 이용한 반복전략은 어느 때 효과가 있을까?
요런 점화식을 본적이 있다면 이해가 빠를것입니다. 제일 만만해보는 유형3을 보면서 이야기 해볼게요.
유형3 점화식처럼 호출되는 함수의 값이(여기선 a(n+1))이 다른 인자를 넣은 함수로 표현되는 경우에 (여기선 p*a(n)+q)) 재귀함수를 쓰기 딱 좋습니다. 왜냐하면 위에서 보면 알 수 있다시피 재귀함수는 top down으로 함수를 호출합니다. 점화식을 풀 때도 n번째 수열을 n번째 앞의 수들의 함수로 표현함으로써 풀어냅니다. 둘의 논리적 풀이구조는 같군요. 그래서 직관적으로 바로 재귀함수를 쓰는게 편합니다. 실용적인 면으로 보자면 점화식이 조금만 복잡해도 사람이 수학으로 풀기는 힘듭니다. 그런데 컴퓨터가 있다면 말은 달라지죠. 어떤 점화식이든 재귀함수를 이용하면 풀어낼 수 있으니까요. 물론 메모리를 엄청나게 잡아먹기야 하겠지만 따로 캐시작업을 한다면 메모리를 줄이면서 할 수도 있을겁니다.
이것외에 재귀함수를 이용한 반복전략과 반복문을 이용한 반복전략의 차이는 메모리 소모에 있습니다. 재귀함수를 호출 할 때는 재귀함수가 여러개 호출되어 있고 계산과정을 추적해야하기 때문에 메모리가 더 많이 소모되는 편입니다.
더 간결하게 가독성이 뛰어나고 멋있게(?) 할 수 있는 장점은 있으나 자칫 알고리즘의 효율이 낮아질 수 있는 것이죠.
참고문헌
1. 한 권으로 그리는 컴퓨터 과학 로드맵, 지은이 : 블라드스톤 페헤이라 필루 옮긴이 : 박연오 76P-79P
2. 점화식사진
