[JAVA] 재귀 기초 - 피보나치 (Fibonacci)

재귀에 대한 이해도가 전혀 없다면 

http://marobiana.tistory.com/79   <- 팩토리얼을 먼저 보면 이해가 쉬울 것이다.

그것보다 조금 더 응용된게 피보나치.

피보나치는 팩토리얼보다 조금 어렵지만, 원리를 이해하면 어렵지 않다.

근데 재귀는 워낙 복잡해서 처음 접하는 사람에게는 설명하기도, 이해하기도 어렵다ㅠ_ㅠ 

(복잡한 재귀문제 풀다보면 아무리 이해도 높은 사람도 멘붕오고 짜증남 ㅋㅋㅋㅋㅋ)

1. 피보나치(Fibonacci)란?

피보나치는 수열 종류 중 하나이다.

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

앞에 있는 숫자와 그 앞에 있는 숫자와 더한 것을 나열하는 것이다.

1+1 = 2

2+3 = 5

3+5 = 8

5+8 = 13

..  

이런 식으로

2. 재귀 예제

문제 : 피보나치 수열을 입력 받은 숫자 개수만큼 출력하라

public class Fibonacci { public static void main(String[] args) { int input = 8; // 8개 출력 for (int i = 1; i <= input; i++) { System.out.println(fibo(i)); } } public static int fibo(int n) { if (n <= 1) return n; else                          return fibo(n-2) + fibo(n-1); } }

>> 결과

1 1 2 3 5 8 13 21

3. 원리 

i	1	2	3	4
피보나치 수열	1	1	2	3

fibo(3) 이었을 때 구하는 과정을 생각해보자.

fibo(3-2) + fibo(3-1) 이었다.

즉, fibo(1) + fibo(2) 

fibo(4) 였을 때는? 

fibo(2) + fibo(3)  이었다.

이것을 따로 놓고 봐보자.

간단히 말하면

fibo(2) 했을 때 나온 값과, fibo(3)했을 때 나온 값을 더한게 fibo(4) 인 것이다..

프로그램 안에서 내부적으로 fibo(3), fibo(2), fibo(1).... 을 구해가기 때문에 디버깅이 복잡하지만

원리는 이것이다. 

4. 디버깅

피보나치의 경우는 자기 자신을 두번 부르므로 좀 헷갈릴 수 있다. 정신 차리고 봐야함.. 

1) main에서 i=1 이므로, fibo(1)이 처음으로 불린다.

n이 1과 같으므로 첫번째 이프문에서 1이 return되고 종료

main에서 1이 출력된다.

2) main에서 i=2 이므로, fibo(2)가 불린다.

n이 2이므로 else를 타고, 재귀로 호출이 되기 시작한다...

fibo(2)가 종료되지 않은 상태로 스택에 쌓이고,

Stack

fibo(2-2)

fibo(2)

fibo(n-2) + fibo(n-1)   =>   fibo(2-2) + fibo(2-1)

else문의 첫번째 메소드인 fibo(2-2)가 호출 된다. 

3) fibo(2-2)

n은 0이므로 if문에서 0리턴하고 종료

fibo(2-2) + fibo(2-1)  => 0 + fibo(2-1)

4) 스택에 있던 fibo(2)로 다시 돌아가서, fibo(2-1)이 실행된다.

n이 1이므로 1을 리턴하고 종료된다.

5) 스택에 있던 fibo(2)에서는

fibo(2-2) + fibo(2-1)  =>  0 + 1

else문에서 각각 리턴된 0과 1을 더한 1을 리턴하고 종료된다.

현재, 아래와 같이 출력된 상황임.

1 1

6) main 함수에서는 i는 3이 되어, fibo(3)이 호출된다.

n이 3이므로 스택에 fibo(3)이 쌓이고, else의 fibo함수가 불리게 된다.

Stack

fibo(3-2)

fibo(3)

fibo(3-2) + fibo(3-1)

첫번째 메소드인 fibo(3-2)가 수행된다.

n은 1이므로 1이 리턴되고 종료됨.

fibo(3-2) + fibo(3-1)  =>  1 + fibo(3-1)

7) fibo(3)의 else에 있던 두번째 메소드인 fibo(3-1) 이 수행된다.

n이 2이므로, else를 타게 되고, 이 안에서 또 재귀가 호출된다.

Stack

fibo(2-1)

fibo(2-2)

fibo(3-1)

fibo(3)

8) fibo(3-1)에 대한 재귀 실행. 

fibo(2-2) + fibo(2-1)  =>  0 + 1 = 1

fibo(2-2)는 0이므로 0을 리턴하고 종료.

fibo(2-1)은 1이므로 1을 리턴하고 종료.

1을 최종적으로 리턴.

9) 6번에서 구하던 것을 다 구했다.

1 + fibo(3-1)   = > 1 + 1 = 2

스택에 남아있던 fibo(3)으로 돌아간다.

최종적으로 2를 리턴하게 되어, 메인함수에서 2를 출력하게 된다.

현재, 아래와 같이 출력된 상황임.

1 1  2

10) main함수에서 i가 증가되어 fibo(4)가 호출된다.

원리를 알면 쉽지만, 따라가면서 쓰는 나는...여기서부터 멘붕ㅋㅋㅋㅋㅋ

fibo(4)의 else문,

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

스택에 fibo(4)가 쌓이고, 첫번째 메소드인 fibo(4-2)가 호출된다.

Stack

fibo(4-2)

fibo(4)

* fibo(4)는 결국 fibo(2) + fibo(3) 이므로, 

fibo(2)가 되는 과정이었던 2번과

fibo(3)이 되는 과정인 6번에서 나온 값을 서로 더하는 것이다.

11) fibo(4-2) 수행.

n이 2이므로 else문을 통해 또 재귀가 호출 된다.

fibo(2-2) + fibo(2-1)

Stack

fibo(2-2)

fibo(4-2)

fibo(4)

Stack

fibo(2-1)

fibo(4-2)

fibo(4)

아래와 같이 계산 됨. 계속 위에서 반복했던 내용이므로 설명 않겠음.

fibo(2-2) + fibo(2-1)    =>  0 + 1 = 1

12) 지금 fibo(4)에 대한 첫번째 메소드의 값을 구했다.

fibo(4-2) + fibo(4-1)   =>  1 + fibo(4-1)

이제 fibo(4-1)을 구할 차례이다.

13) fibo(4-1)을 수행한다.

n이 3이므로 else를 타게되고, fibo(4-1)은 스택에 쌓인다.

Stack

fibo(3-1)

fibo(3-2)

fibo(4-1)

fibo(4)

또 재귀가 호출될 것이다.

첫번째 메소드는 n이 1이니 1일것이고, 

두번째 메소드인 fibo(3-1)는 또 재귀호출이 될 것이다.

fibo(3-2) + fibo(3-1)  => 1 + fibo(3-1)

14) fibo(3-1) 수행

스택은 아래와 같은 과정을 거친 후, 

Stack

fibo(2-2)

fibo(3-1)

fibo(4-1)

fibo(4)

Stack

fibo(2-1)

fibo(3-1)

fibo(4-1)

fibo(4)

아래 같은 값을 리턴 받는다. fibo(2)와 같다. 

fibo(2-2) + fibo(2-1)  =>  0 + 1 =  1

스택에 있던 fibo(3-1)에 대한 값은 0+1로 리턴한다.

15) 스택에 있던 fibo(4-1)이 리턴될 차례이다.

위에서 받은 fibo(3-1)의 값과 아까 구한 1과 더한다.

fibo(3-2) + fibo(3-1)  => 1 + fibo(3-1) => 1 + 1 = 2

16) 마지막으로 fibo(4)로 돌아가서 여태 리턴받은 값을 더해서 리턴한다.

else  return fibo(4-2) + fibo(4-1)

(12번 참조)

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

현재, 아래와 같이 출력된 상황임.

1 1  2 3

이제 더 쓸 생각 없다 ㅋㅋㅋ 이런식으로 다음 것도 돌아간다. (충분히 힘들었음)