Java의 재귀 피보나치 시퀀스

피보나치 수열

0과 1에서 시작하는 마지막 두 숫자를 더하여 구성되는 시퀀스입니다. n 번째 요소를 찾으려면 (n-1) 및 (n-2) 항을 더하여 숫자를 찾습니다. 여기서 n은 0보다 커야합니다.

재귀

재귀는 동일한 최종 함수 또는 프로 시저가 종료 조건을 만날 때까지 여러 번 자신을 호출하는 프로세스입니다. 종료 조건을 지정하지 않으면 메서드는 무한 루프 상태로 들어갑니다.

Java의 재귀 피보나치 시퀀스

아래 주어진 코드에서main()메소드는 클래스에 정의 된 정적 함수getFibonacciNumberAt()를 호출합니다. 이 함수는 피보나치 수를 평가하고자하는 수를 정의하는 매개 변수를 취합니다. 함수에는 원하는 조건을 충족 할 때 0 또는 1을 반환하는 기본 검사가 있습니다. 그렇지 않으면 함수는 전달 된 매개 변수를 감소시켜 자신을 다시 호출합니다.

package recursiveFibonacci;

public class RecursiveFibonacciSequence {
  public static void main(String[] args) {
    int fibonacciNumber = getFibonacciNumberAt(6);
    System.out.println(fibonacciNumber);
  }

  public static int getFibonacciNumberAt(int n) {
    if (n == 0)
      return 0;
    else if (n == 1)
      return 1;
    else
      return getFibonacciNumberAt(n - 1) + getFibonacciNumberAt(n - 2);
  }
}

출력:

8

자세한 평가는 아래에서 볼 수 있습니다.

getFibonacciNumberAt(6) = getFibonacciNumberAt(5) + getFibonacciNumberAt(4); //5+3=8
getFibonacciNumberAt(5) = getFibonacciNumberAt(4) + getFibonacciNumberAt(3); //3+2=5
getFibonacciNumberAt(4) = getFibonacciNumberAt(3) + getFibonacciNumberAt(2); //2+1=3
getFibonacciNumberAt(3) = getFibonacciNumberAt(2) + getFibonacciNumberAt(1); //1+1=2
getFibonacciNumberAt(2) = getFibonacciNumberAt(1) + getFibonacciNumberAt(0); //1+0=1
If, getFibonacciNumberAt(1) = 1;
And getFibonacciNumberAt(0) = 0;

위의 프로그램을 수정하여 원하는 수까지 시리즈를 인쇄 할 수 있습니다.

package recursiveFibonacci;

public class RecursiveFibonacci {
  public static void main(String[] args) {
    int maxCount = 10;
    for (int i = 0; i <= maxCount; i++) {
      int fibonacciNumber = printFibonacci(i);
      System.out.print(" " + fibonacciNumber);
    }
  }

  public static int printFibonacci(int n) {
    if (n == 0)
      return 0;
    else if (n == 1)
      return 1;
    else
      return printFibonacci(n - 1) + printFibonacci(n - 2);
  }
}

출력:

0 1 1 2 3 5 8 13 21 34 55