처음에 c를 공부할때 재귀에 대해 이해하기가 매우 힘들었다.
어떤 구조로 왜 작동하는지에 대해 이해하지 못했다.
처음 접하는 분들을 위해 이해하기 쉽게 자세하게 설명해 보겠다.
재귀함수의 정의는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.
예를들어
int recur(){
return recur();
}물론 이런 함수는 없지만 이런식으로 함수안에서 자신의 함수를 다시 리턴하는 것을 말한다.
피보나치가 재귀함수에 좋은 예시로 많이 쓰인다.
피보나치를 재귀함수로 구현하면 다음과 같다.
#include <stdio.h>
int fibonacci(int num){
if(num == 1||num == 2) return 1;
else return fibonacci(num-1)+fibonacci(num-2);
}
int main(void){
//7번째 수 까지 구한다.
for(int i = 1; i <= 7; i++){
printf("%d 번째 수:",i);
printf("%d\n",fibonacci(i));
}
return 0;
}피보나치는 기본적으로 f(n) = f(n-1)+f(n-2) 의 특성을 가진다.
또한, f(1),f(2)는 1이다.
f(n)의 n은 피보나치에서 몇번째 숫자인지를 의미한다.
위의 코드를 예시로 들어보자.
f(1)과 f(2) 는 1이다.
f(3) = f(2)+f(1)
f(4) = f(3)+f(2)
...
f(7) = f(6)+f(5)
이런식으로 구현되어 있다.
더 자세하게 들여다 보면
f(5)의 경우에 f(4)+f(3) = (f(3)+f(2)) + (f(2)+f(1)) = (f(2)+f(1))+f(2)+(f(2)+f(1)) 이다.
코드로 살펴보면
f(4)는 num이 1이나 2가 아니기때문에 else로 넘어간다.
여기서는 재귀적으로 return을 해주는데,
return fibonacii(n-1)+fibonacci(n-2)에서 fibonacci(n-1)로 들어간다.
즉, fibonacci(3)을 수행하게 된다.
if 문에서 num(3)은 1이나 2가 아니기 때문에 다시, return fibonacii(n-1)+fibonacci(n-2)로 가서 fibonacci(n-1)로 들어간다.
fibonacci(2)를 수행하게 된다.
if 문에서 num이 2이기때문에 return 1을 해준다.
return이 되었으므로, 이번에는 fibonacci(n-2)를 수행한다.
즉 f(1)을 수행하고 return 1을 해준다.
그러면 이제 f(2)+f(1)을 수행하게 했던 f(3)을 return 해야하는데 f(2)+f(1)을 해주어서 2가 된다.
f(3)은 f(4)에서 return 해주었던 f(n-1)이었다.
f(n-1)을 return 해주었으므로, 이번에는 f(n-2)를 수행한다.
f(n-2)는 f(2)이므로 1을 return 한다.
이제 return f(3)+f(2)을 해준다. 2+1이므로 3이된다.
f(4)는 3이 되었다.
f(4)는 맨처음 시작했던 f(5)의 리턴값이었다. 즉, f(5) = f(4)+f(3)이었다.
f(4)는 return 되었으므로 이제 f(3)을 return 해준다. f(3)도 위의 과정과 동일하게 수행하며, return 값은 2가된다.
최종적으로 f(5) = f(4)+f(3)을해서 5를 리턴해준다.
그림으로 보면 다음과 같은 순서로 return을 한다.
f(n)는 fibonacci(n) 이다.
그림을 그려가면서 공부하면 빠르게 이해할 수 있다.
