백준 10870번 피보나치 수 5(Java)

피보나치의 수를 구하는 문제. f(n)=f(n-1)+f(n-2)가 성립하기에 이를 기반으로 풀면되는 쉬운 문제이다.

이때 재귀의 특징상 메모리의 낭비가 심한데 낭비를 줄이는 방법은 위 사진에 나와있듯이 f(19)=f(17)+f(18)이다. 그런데 f(18)을 구하는데 f(17)의 값을 계산한 적이 있으므로 f(17)의 값을 어딘가로 빼놓고 f(19)를 계산할 때 f(18)과 f(17)을 더해 계산하면 메모리를 절반가량 아낄 수 있다. 다만 이 풀이법에서는 아직 구현하지 않았다.

import java.util.Scanner;

public class Main {

    int fibo(int count){
        if(count==0)
            return 0;
        if(count==1)
            return 1;
        return fibo(count-1)+fibo(count-2);
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int count=scanner.nextInt();
        Main bae=new Main();
        System.out.println(bae.fibo(count));
    }
}