[대표문제] 피보나치 수열

재귀 호출

[대표문제] 피보나치 수열

---

피보나치 수열

• 이전의 두 수 합을 다음 항으로 하는 수열

  점화식

  A0 = 0
  A1 = 1
  Ai = Ai-1 + Ai-2 (i >= 2)

  재귀함수를 사용한 피보나치 수열

• 수도 코드

  /*
  fibo(n)
      if n < 2 : return n;
      else : return fibo(n-1) + fibo(n-2); 
  */

• 자바 코드1; 단점. 중복 호출이 매우 많음. 최적화 필요

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class Java4150_피보나치수 {
      static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  
      public static void main(String[] args) throws IOException {
          int n = Integer.parseInt(bf.readLine());
  
          System.out.println(fibo(n));
      }
  
      private static int fibo(int n) {
          if(n < 2) return n;
          return fibo(n-1) + fibo(n-2);
      }
  }

• 자바 코드2; 반복문을 이용한 해결

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class Java4150_피보나치수 {
      static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  
      public static void main(String[] args) throws IOException {
          int n = Integer.parseInt(bf.readLine());
          int F0=0, F1=1, F2=1;
  
          /*
          F(n) = F(n-2) + F(n-1); n>=2
           */
          for(int i=2; i<=n; i++) {
              F2 = F1 + F0; // 피보나치 수열 계산
              F0 = F1; // F0 갱신
              F1 = F2; // F1 갱신
          }
  
          System.out.println(F2);
      }
  }

• 자바 코드3; DP를 이용한 해결