[재귀함수] 피보나치 수열 .java

문제

피보나키 수열을 출력한다

피보나치 수열이란 앞의 개의 수를 합하여 다음 숫자가 되는 수열이다

 

입력은 피보나치 수열의 총 항의 수 이다

만약7 이 입력되면 1 1 2 3 5 8 13을 출력하면 된다

입력

첫 줄에 총 항수 N(3<=N<=45) 이 입력된다

출력

첫 줄에 피보나치 수열을 출력합니다

입력

10

출력

1 1 2 3 5 8 13 21 34 55

 

내 풀이

n은 항의 번호

 

 

1. dfs값을 따로 저장하지 않고 매번 호출하는 코드

import java.util.Scanner;


public class Main {
	
	public static int dfs(int n) {
		if(n==1) return 1;
		else if(n==2) return 1;
		else return dfs(n-2) + dfs(n-1);
	}
    public static void main(String[] args) {
    	
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        for(int i = 1; i <=n; i++) {
        	System.out.print(dfs(i) + " ");
        }
        
    }

}

 

 

2. dfs값을 배열로 저장해서 불필요한 호출을 없앤 코드

-> 배열에 저장한 값을 리턴

 

import java.util.Scanner;


public class Main {
	static int[] fibo;
	public static int dfs(int n) {
		if(n==1) return fibo[n]=1;
		else if(n==2) return fibo[n]=1;
		else return fibo[n]=dfs(n-2) + dfs(n-1);
	}
    public static void main(String[] args) {
    	
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        fibo = new int[n+1];
        
        dfs(n);
        for(int i = 1; i <=n; i++) {
        	System.out.print(fibo[i] + " ");
        }

        
    }

    
}

 

3. 메모이제이션(Memoization)

• 중복된 계산을 방지하여 효율성을 높이는 방법
• 이미 계산한 결과를 저장해 두고, 같은 계산이 필요할 때 저장된 결과를 재사용
• 동적 계획법(Dynamic Programming)의 일종

=> 이미 계산한 값을 배열에 저장 -> 구하려는 값이 이미 계산한 결과면 배열에서 해당 값 리턴

import java.util.Scanner;


public class Main {
	static int[] fibo;
	public static int dfs(int n) {
		//이미 구해져 있다면
		if(fibo[n] >0) return fibo[n];
		if(n==1) return fibo[n]=1;
		else if(n==2) return fibo[n]=1;
		else return fibo[n]=dfs(n-2) + dfs(n-1);
	}
    public static void main(String[] args) {
    	
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        fibo = new int[n+1];
        
        dfs(n);
        for(int i = 1; i <=n; i++) {
        	System.out.print(fibo[i] + " ");
        }

        
    }

    
}

 

 

• for문 VS 재귀

: for문이 더 효율적, 재귀는 스택 프레임이 계속 생기기 때문