개발/알고리즘 & 자료구조

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

신매력 2013. 6. 20. 21:12

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

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. 원리 


1

피보나치 수열


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


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

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

2

3




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