n-th Fibonacci Term (Recursive)

1. Problem

- 피보나치 수열에서 n번째 수를 재귀함수를 이용해 찾아보자

 

2. Input

1) 음이 아닌 정수 n

 

3. Output

1) n번째 피보나치 수

 

4. PseudoCode

int fib(int n){
    if(n<=1)
        return n;
    else
        return fib(n-1) + fib(n-2);
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int a = 7;
    	System.out.println(a + "번째 피보나치 수: " + fib(a)); // 7번째 피보나치 수: 13
    }
    // 피보나치 수열(0번째~10번째)
    // 0 1 1 2 3 5 8 13 21 34 55
    
    static int fib(int n) {
    	return n<=1 ? n : fib(n-1)+fib(n-2);
    }
}

- T(n) > 2^(n/2)