[43일차] 피보나치 수열을 재귀로 구현하기

저요·2022년 11월 4일

2022 100th day challenge

목록 보기

43/97

서론

오늘의 목표

피보나치 수열이란?

피보나치 수열을 재귀로 구현하기

리뷰

본론

피보나치 수열이란?

1. 피보나치 수열(Fibonacci sequence)

피보나치 수열이란, 어떤 수열의 항이 앞에 두 항의 합과 같은 수열을 말한다.

이탈리아의 수학자 피보나치가 발견한 것으로, 피보나치는 1202년 갓 태어난 암수 한 쌍의 토끼가 있을때 이 토끼 한쌍이 태어난지 두 달이 되는 달부터 매달 암수 한 쌍의 토끼를 낳으며, 새로 태어난 토끼 한 쌍도 태어난지 두 달이 되는 달부터 매달 암 수 한 쌍의 토끼를 낳을때 일년 뒤에 이 토끼는 모두 몇 쌍이 되는지 자신의 저서에서 문제를 제시했다.

토끼들의 번식을 수열로 나타내면 다음과 같은 모양이 되는데

1,1,2,3,5,8,13,21,34,55,89,144,233,377 ...

이걸 피보나치 수열이라고 한다.

2. 피보나치 수열의 특징

앞에 두 항을 더하면 다음 항의 수를 계산할 수 있다.
어느 숫자건 앞으로 한 항 건너 숫자로 나누면 몫이 2가 된다.
바로 앞 항의 숫자로 뒷항의 숫자를 나누면 황금비가 나온다.
뒤로 한 항 더 큰 숫자를 나누면 2.618에 근접하게 된다.
인접한 두 항의 최대공약수는 1이다.

3. 피보나치 수열의 점화식

문제

인자로 받은 숫자가 가리키는 피보나치 수열에서의 값을 구하시오.

솔루션

function fib(nth){
  //nth번째에 있는 피보나치 수열의 숫자를 구하기
  //두번째 부터는 1로 세팅한다.
  if(nth <= 2) return 1;
  return fib(nth-1) + fib(nth-2);
}

이렇게 구현하면 어떤 식으로 값이 도출되는지 알아보자 만약 4를 파라미터로 입력했다면 기대값은 3이다.

//첫번째 호출
fib(3) 				+ fib(1)
//두번째 호출
fib(2) + fib(1)		//return 1
//세번째 호출
//return 1 + return 1

첫번째 함수를 호출했을때 fib는 2보다 크기 때문에 if문에서 걸리지 않고 다음 단계로 넘어가, 두번째 호출을 하게 된다.
두번째 호출에서 첫번째 호출 때의 마지막 항은 -2를 한 1의 값으로 함수를 호출해 1을 반환하게 되고, 나머지는 3으로 호출했기 때문에 다시 한번 마지막으로 세 번째 호출을 하게 된다.
따라서 계산은 다음과 같다.
값이 리턴되면서 스택은 위에서부터 아래로 차례대로 값을 전달함과 함께 계산이 이루어진다.