recursion_basic. 피보나치 수열 1

dwanGim·2022년 5월 11일
0

recursion_basic

목록 보기
1/1
post-thumbnail

피보나치 수열

피보나치 수열은 처음에는 0

두번째 열에는 1

세번째 열부터는 첫번째 열과 두번째 열을 더한 값

네번째 열에서 두번째 열과 세번째 열을 더한 값을 나열하는

수열이다.

자바 코드로 이 수열을 구현하면 다음과 같다.

package com.ict.recursion;

public class RecursiveFibonacci {
	
	public static int  fibo(int num) {
		
		if(num == 1) {
			
			return 0;
			
		} else if(num == 2) {
			
			return 1;
			
		} else {
			
			return fibo(num - 1) + fibo(num - 2);
			
		}
	}
	
	public static void main(String[] args) {
		
		System.out.println(fibo());

	}
	
}

if문으로 감싸서
num이 1이면 0;
num이 2이면 1;
else는 모두 num - 1과 num - 2한 fibo값을 호출하여

더하는 로직이다.

main에서 fibo() 안에 값을 넣어 호출해주면

콘솔에 찍힌 값을 확인할 수 있다.

먼저 24번 라인 메인에서 fibo(5)를 호출한다.

5번 라인의 fibo()에 5의 값을 주고 시작된다.

15번 라인 else {

로 내려가 return fibo(5 - 1) + fibo(5 - 2);를

만난다.

좌변의 fibo(4)이 먼저 호출된다.

fibo(4)는 다시 fibo(3)과 fibo(2)를 호출한다.

좌변의 fibo(3)이 먼저 실행된다.

fibo(3)도 역시 fibo(2)와 fibo(1)을 호출한다.

둘은 각각 1과 0이기 때문에 둘을 합한 값은 1이다.

fibo(3)에 1이 대입되어 드디어 리턴값을 돌려주러 가게된다.

이러한 과정을 그림판으로 그려보면 이렇다.

조잡한 그림이지만 그리면서 재귀의 개념을

조금은 확실하게 이해할 수 있다.

재귀함수가 정확히 무엇인지는

다음 시간에 상세히 다루도록 하겠다.

profile
배울 게 참 많네요.

0개의 댓글