(JAVA)백준 알고리즘 No.10870

http://boj.kr/10870

재귀 : 피보나치 수열 f(3) = f(2) + f(1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int result = fibo(n);
		System.out.println(result);
	}
	
	public static int fibo(int n) {
	
		if(n==0) {
			return 0;
		}
		
		if(n==1) {
			return 1;
		}
		
		if(n>=2) {
			return fibo(n-1) + fibo(n-2);
		}
		return 0;
	}
}

시간복잡도 : 만약 n이 10일경우 fibo(10)=fibo(9)+fibo(8)
fibo(9) > fibo(8) 과 fibo(7)을 호출
fibo(8) > fibo(7) 과 fibo(6)을 호출
즉, fibo(1)은 n번 호출 fibo(2)는 n-1번 호출되며 ... fibo(n)은 1번 호출된다.
O(n^2)

피보나치 수열을 O(n)으로 구현하는 방법도 있습니다.
한번 구현한 수를 배열에 저장시키고 다음 연산에 사용.
O(n)으로 구현하기