오늘, 다니는 국비학원에서 실습 문제를 풀다가 재귀함수의 벽에 부딫혔다.
재귀함수도 여러 종류가 있는데 피보나치.. 에서 벽을 느껴버렸다.

알고리즘 부분이 많이 부족한 본인 (수학적 사고력 부족) 이라, 이 피보나치가 재귀에 있어서는 Hello World 격이라고 알고있는데, 답을 봐도 이해가 안갔다.

그래서 차근 차근 이해하는 과정을 기록해보려고한다.

피보나치 수열?

피보나치 수열이란, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

1, 1, 2, 3, 5, 8, 13, 21 . . .

이런식으로 진행하는 수열이다.

이 피보나치를 코드로 나타내면 다음과 같다.

	public static int fibonacci(int num) {
		int result = 0;
		
		if(num == 1) {
			result = 1;
		} else if (num == 2) {
			result = 1;
		} else if (num >= 3) {			
			result = fibonacci(num -2) + fibonacci(num - 1);
		}
		
		return result;
	}

요렇게 생겼다. 보면 fibonacci 메서드가 내부에서 다시 셀프로 호출되고 있는 모습을 확인 할 수 있는데, 이게 재귀함수 라고 불리는 형태이다.

매개변수로 num을 받고있고, 이 num은 피보나치 수열의 항을 의미한다.
즉 다음 메서드는 피보나치 수열의 num 번째 항의 값을 반환하는 함수이다.
그래서 이게 어떻게 작동하는가..?

우선 num이 1 또는 2 일때는 무조건 1을 return 한다. 피보나치 수열의 첫번째, 두번째 항은 무조건 1 이니까!

천천히 3부터 늘려가면서 이 함수의 구조를 이해해보자.

3을 넣었다고 생각하고 코드를 다시 적어보면,

	public static int fibonacci(int num) {
		int result = 0;
		
		if(num == 1) {
			result = 1;
		} else if (num == 2) {
			result = 1;
		} else if (num >= 3) {	// 3행
			result = fibonacci(1) + fibonacci(2);
		}
		
		return result;
	}

result = fibonacci(1) + fibonacci(2)
result = 1 + 1
result = 2

fibonaccit(3) 은 2를 반환하게 될것이다.

자 이제 숫자 하나를 올려서 num이 4라고 가정하고 다시 한번 흐름을 분석해보자.

	public static int fibonacci(int num) {
		int result = 0;
		
		if(num == 1) {
			result = 1;
		} else if (num == 2) {
			result = 1;
		} else if (num >= 3) {	// 4행
			result = fibonacci(2) + fibonacci(3);
		}
		
		return result;
	}

fibonacci(2) + fibonacci(3) -> 1 + 2
fibonacci(4) = 3

이제 5행의 값을 알아보자. 이제 슬슬 패턴이 보이게 될 것 이다.

	public static int fibonacci(int num) {
		int result = 0;
		
		if(num == 1) {
			result = 1;
		} else if (num == 2) {
			result = 1;
		} else if (num >= 3) {	// 5행
			result = fibonacci(3) + fibonacci(4);
		}
		
		return result;
	}

fibonacci(3) + fibonacci(4) -> 2 + 3
fibonacci(5) = 5

이런식으로 진행된다. 마지막으로 6행까지만 해보자!

	public static int fibonacci(int num) {
		int result = 0;
		
		if(num == 1) {
			result = 1;
		} else if (num == 2) {
			result = 1;
		} else if (num >= 3) { // 6행
			result = fibonacci(4) + fibonacci(5);
		}
		
		return result;
	}

fibonacci(4) + fibonacci(5) -> 3 + 5
fibonacci(6) = 8

fibonacci(num - 2) + fibonacci(num - 1) 이 코드는 보이는대로, 지금 내가 구하려는 항의 전전 항의값과 전 항의값의 합을 되돌려준다.
이 사실은 위에서 1부터 차례대로 대입해봤으니까 쉽게 알 수 있다.

사실 이게 끝인것같다.. 그냥 1부터 차례대로 대입해보면 이게 어떤식으로 내가 구하려고 하는 n번째 항의 값을 리턴하는구나 알 수 있다.

글을 적기전엔 복잡하게 느껴졌었는데, 1부터 넣으면서 생각하다보니까 이거.. 그렇게 복잡하진 않은것같다.