문제
n번째의 피보나치수열의 값을 구하는 함수를 만든다.
피보나치수열
0과 1로 시작하고 n번째 피보나치 수는 바로 직전의 두 피보나치 수의 합이다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ......
0번째 피보나치 수는 0이고, 5번째 피보나치 수는 5, 10번째 피보나치 수는 55가 된다.
5번째 피보나치 수 5가 나온 과정을 나열해 보면 이렇다.
0
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
즉 다섯 번째 피보나치 수인 5는 다섯 번째 수는 네 번째수와 세 번째 수의 합이고, 네 번째 수는 세 번째 수와 두 번째 수의 합이 된다.
n = (n-1) + (n-2)
(n-1) = (n-2) + (n-3)
(n-2) = (n-3) + (n-4)
이를 함수 식으로 표현하면
조건
- n은 (n-1) + (n-2)를 함수에 넣어서 반복 실행시켜준다.
- n의 값이 0 또는 1이 나오면 실행을 중단한다.
- 함수에 들어오는 인자의 값, n번째 수가 0 또는 1이 될 경우
n번째가 0 이면 => 0
n번째가 1 이면 => 1
function fibonacci(n) {
if ( n <= 1 ) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}함수가 실행되는 과정이 머릿속으로 완벽하게 그려지지 않아서 fibonacci 함수 n의 값으로 5를 넣었을 때를 그림으로 그려보았다.
if ( n <= 1 ) {
return n;
}위의 조건이 될 때까지 함수는 계속해서 실행이 되고, 함수가 반복 실행을 멈추는 순간부터 뒤에서부터 순차적으로 (n-1) + (n-2)의 값을 구하게 된다.
