두 번째 velog
출처 : https://www.acmicpc.net/problem/10870
10일만에 쓰는 velog... 사실 뭘 써야될지 모르겠어서 그냥 뒀다가 갑자기 생각이 났다.
오늘 풀 문제는 피보나치 수! 수학 시간에 한번쯤 접해본 적이 있는 간단한 문제이다.
> 문제
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
코드 (C++)
보통은 for문이나 재귀함수를 써서 구현하는데, 재귀함수가 코드가 훨씬 짧다. 코드는 다음과 같다.
#include <iostream>
using namespace std;
int fibonacci(int n)
{
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int num;
cin >> num;
cout << fibonacci(num) << endl;
}피보나치 수열 자체는 이해를 할 것이 별로 없다... 그냥 맨 처음은 0으로 시작하고, 그 다음은 1이다. 그 뒤로부터는 두 칸 앞의 수와 한 칸 앞의 수를 더한 것이 수열을 이루게 된다.
저런거 처음보는데요?
흰 종이에 0, 1까지 써놓고 0+1=1 | 1+1=2 | 1+2=3 ... 더해봅시다
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 요렇게 나온답니다.
말로 하는 설명
코드에서 헷갈릴만한건 재귀함수의 구현부분인데, 나는 재귀를 처음 접했을 때 어떻게 돌아가는지 몰라서 한참 헤맸었다. 디버깅을 해보고 나서는 어렴풋이 이해했다.
디버깅을 할때는 메뉴의 디버그->창->자동, 조사식, 호출 스택 등을 사용하면 좋다. 특히 재귀함수 디버깅을 해볼때는 호출스택을 보고 하는 것이 좋다. 디버깅은 F11 누르면서 한칸한칸 전진해보자.
우선 나는 10번째 피보나치 수를 출력하고 싶다. 10을 입력하고 fibonacci(num)함수에 10이 인자로 들어가게 된다.
int fibonacci(int n)
{
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}10은 함수 내 if문에 걸리지 않는다. 그러면 아래의 return 으로 내려간다.
return의 첫번째 항, fibonacci(n-1) 로 들어가게 되는 것이다. 즉, fibonacci(9)를 실행한다.
9도 1보다는 작지 않다. -> 아래 return 으로 내려가 첫번째 항, fibonacci(n-1) 로 들어가 fibonacci(7)을 실행한다.
이 과정을 반복하다보면 fibonacci(1)까지 내려가게 된다. 인자가 1이면 if문에 걸리고, return n; = 1을 리턴한다.
(이 때 호출스택을 보면 뭔가가 차곡차곡 쌓이고 있단 걸 알 수 있다. 1을 리턴하는 순간 호출스택이 한칸 줄어드는 걸 볼 수 있을 것이다.)
그런데 fibonacci(1) 은 어디에서 실행된걸까?
바로 fibonacci(2) 일때 return fibonacci(n-1)+fibonacci(n-2); 식의 앞 항으로 들어간 것이다.
fibonacci(n-1) 은 리턴을 받아(2-1=1) 빠져나왔으므로 뒷 항인 fibonacci(n-2) 로 들어간다. fibonacci(0)의 반환값은 0이다.
이제 fibonacci(2)를 구했다! 그러면 이제 어디로 갈까?
fibonacci(3) 에서 fibonacci(n-1) 항으로 들어가 fibonacci(2)를 구한것이므로, 앞 항을 빠져나와 뒷 항인 fibonacci(n-2) 항으로 들어가게 된다. 그러면 fibonacci(1)을 다시 구하는 것이다.
이 과정을 반복하면, fibonacci(10) 의 값을 리턴하게 되는 것이다.
호출 스택이 차곡차곡 쌓였다가 사라졌다가 하는 과정을 주시해보면 재귀함수의 원리를 알 수 있다.
모르겠으면 디버깅 - F11과 친해져보아요
제출을 해보도록 하실까
성공이얌
