재귀 - 피보나치

문제풀이

문제에 나와있는 식을 참조하거나 피보나치 수열에 대해 알고 있다면 쉽게 풀 수 있는 문제일 것이다.

1. 문제에 나와 있는 식 F(n) = F(n-1) + F(n-2) (n>=2)과 0번째 피보나치 수는 0, 1번째 피보나치 수는 1이다.를 이용하여 문제를 푼다.
2. 앞서 말했던 조건을 가지고 N>=2 인 경우와 N = 0인 경우, N = 1인 경우의 조건에 따라 알맞게 구현한다.

소스 코드

package recursion;

import java.util.*;

public class fibonacci {

public static void main(String[] args) {
	// TODO Auto-generated method stub

	Scanner in = new Scanner(System.in);
	
	int n = in.nextInt();
	
	int ans = fibo(n);
	
	System.out.println(ans);
}

public static int fibo(int N) {
	if(N >= 2) {
		return fibo(N-1) + fibo(N-2);
	}
	else if(N == 0)
		return 0;
	else
		return 1;
	
}

}

문제를 풀고 느낀점

• 우선 피보나치 수열에 대해 알고 있었고, 문제에 답이 있는 경우 이므로 재귀함수를 알고 문제의 조건들만 앎맞게 구현한다면 굉장히 쉽게 풀 수 있는 기본 문제였다.