[백준] 피보나치 수 5

🔗 문제로 이동 👉 [피보나치 수 5]

TIP 재귀 함수를 사용해서 풀어보기

☑️ 첫 번째 풀이

피보나치 수는 바로 앞 두 피보나치 수의 합 이기 때문에(2번째 피보나치의 수 이상), 재귀 함수를 호출할때 몇 번째 호출인지 나타내는 정수 cnt, 첫번째 수 a, 그 다음 수 b를 인자로 담아서 넘겨주었다.
시간이나 메모리 측면에서 나쁘진 않으나 피보나치 수가 0번째 일때 예외처리되는 조건문이 매끄럽지 못해 다시 풀어보았다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
     
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        if(n == 0) System.out.println(0);
        else System.out.println(recursion(n, 0, 1));
        
    }
    
    public static int recursion(int cnt, int a, int b) {
        
        int sum = a + b;
        if(cnt < 3) return sum;
        
        return recursion(cnt - 1, b, sum);
        
    }
    
}

✅ 두 번째 풀이

첫 번째 풀이에선 int sum = a + b; 로 두 수를 합쳐줬다면,

두 번째 풀이에선 합치는 과정을 아예 recursion(num-1) + recursion(num-2); 으로 정의해줬다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        System.out.println(recursion(n));
        
    }
    
    public static int recursion(int num) {
        
        if(num == 0) return 0;
        else if(num == 1) return 1;
        else return recursion(num-1) + recursion(num-2); // Here!
        
    }
    
}