210402. Today I Learned(TIL) : 재귀(피보나치 수열) 문제 풀이

재귀함수의 대표적인 케이스인 피보나치 수열 문제를 풀어보았다.

문제: 수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0,1,1,2,3,5,8,13,21,34,55...

입력: number 타입의 num (num은 0 이상 15 이하의 정수)

출력: number 타입을 리턴해야 합니다. (num 번째 피보나치 수)

주의사항:

• 함수 fibonacci는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 피보나치 수열은 0번부터 시작합니다.

먼저 피보나치 수열은 0과 1로 시작해서 다음번에 올 수는 직전 두 수의 합으로 이루어지는 수열이다. 예를 들어 let arr = [0,1,1,2,3]의 구조를 살펴보면, 0과 1로 시작해서 2번째 인덱스의 수는 0+1=1이다. 마찬가지로 3번째 인덱스의 수는 1+1=2이며 4번째 인덱스의 수는 1+2=3이다. 이 구조를 코드로 표현하면 다음과 같다.

arr[i] = arr[i-1] + arr[i-2]

이제 이 구조를 재귀함수를 이용해서 피보나치 수열을 리턴하는 함수의 기능을 구현할 것이다.

우선 가장 작은 단위의 리턴값을 할당해주어야 한다.

if(num === 0) {
	return 0;
    }

0부터 시작해서 차례로 값을 돌려주며 돌아오기 때문에 인자 num에 0을 입력받으면 number 타입의 숫자 0을 리턴해야 한다. 일반 수열에서는 초기값이 1개이지만 피보나치 수열에서는 0과 1의 초기값은 고정이기 때문에 1을 입력받았을 경우의 리턴값도 정해주어야 한다.

else if(num === 1) {
	return 1;
    }

이제 전체 코드를 작성해보자.

function fibonacci(num) {
	if(num === 0) {
    		return 0;
        	}
    	else if(num === 1) {
    		return 1;
       		}	
    	else {
    		return fibonacci(num-1) + fibonacci(num-2);
        	}
      	}  

위에서 분석한 구조의 식을 재귀의 형태로 써주면 초기값 설정과 반복할 식 작성에 문제없이 성립된다. 자기 자신 함수를 계속 호출하다가 인자로 받는 num의 수가 0 또는 1이 되는 순간 그 리턴값을 가지고 차례대로 되돌아오며 최종값을 리턴하게 된다.
이번 문제는 arrSum과는 또 다른 구조의 재귀함수 케이스를 살펴보기에 아주 좋은 예제였다. 다음 시간에는 고차함수의 다양한 메소드들의 기능을 살펴볼 예정이다.