자 코딩 하면 이게 빠질 수 없죠! 바로 피보나치 수열!
죄송합니다;;; 이건 피보나치 수열에 대한 아주 복잡한 식이고요, 이 어지러운 관계식은 저도 이해를 못 합니다. 일반화시키면,
이겁니다^^ 정리해 보면 fibo(n) = fibo(n - 1) + fibo(n - 2)입니다. fibo(1)과 fibo(2)는 1이고요. 그럼 수열은 이렇게 가겠죠?
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
이걸 재귀함수로 나타내 볼겁니다. 이건 재귀함수 안에 재귀함수 옆에 재귀함수가 있어서 조금 어지러울 수 있지만, 한 번 코드를 보여 드리고 해석해드릴게요^^
int fibo(int n){
if (n <= 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}
역시 재귀함수답게 코드가 아주 간단하죠? 해석 들어갑니다!
일단 fibo(5)가 들어왔다고 칩시다. 그럼 일단 5는 2보다 작거나 같지 않죠? 그러니까 fibo(n - 1)로 먼저 넘어갑니다. 그러면 n이 2가 될때까지 작업이 되겠죠? 그럼 4가 또 3하고 2로 나눠지는데 3은 또 2하고 1로 나눠지고 그럼 둘이서 1로 반환이 되고 오른쪽에 나눠져 있던 2도 1로 반환이 되면서 fibo(4)의 값은 3이 됩니다. 그리고 fibo(3)차례죠? fibo(3)은 전에 구했듯이 값이 2입니다. 그러니까 3하고 2하고 더해서 5가 됩니다. 그리고 실제로 비교해보면 1, 1, 2, 3, 5에서 fibo(5)의 값은 5가 맞죠?
이건 재귀함수 안에 재귀함수가 2개 있는 경우입니다. 이럴 때는 많이 복잡해지는데, 이렇게 그림을 그리시면 재귀함수를 이해하시기에 도움이 될 것입니다.
이런 그림을 트리(tree)라고 합니다. 이런 트리 그림을 그리시면 재귀함수의 구조를 알기도 쉽고 프로그램을 실제로 짜실 때 아주 도움이 되실 겁니다. 질문 있으시면 댓글란에 알려주세요!
