[알고리즘 문제]재귀함수를 이용한 피보나치 수열 출력 - DFS

▷ 문제

피보나키 수열을 출력한다.

피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
입력은 피보나치 수열의 총 항의 수이다.

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

* 입력

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

* 출력

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

▷ 입력 예시

10

▷ 출력 예시

1 1 2 3 5 8 13 21 34 55

▷ 풀이

import java.util.Scanner;

public class Main {
    public void solution(int n){
      for(int i=1; i<=n; i++){
        System.out.print(fibonacci(i) + " ");
      }
    }

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

    public static void main(String[] args){
      Main main = new Main();
      Scanner kb = new Scanner(System.in);

      int n = kb.nextInt();

      kb.close();

      main.solution(n);
    }
  }

▷ 메모

• 팩토리얼, 피보나치는 재귀 함수의 대표적인 예제로써 원리는 확실히 짚고 넘어가야 함