[Algorithm] 피보나치 수열 (fibonacci)

참고사이트

오명운님 블로그

1. 피보나치 수열이란?

• '0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...`
• 피보나치 수열은 다음과 같이 정의됩니다.

• f(0) = 0
  f(1) = 1
  f(n) = f(n-1) + f(n-2);

2. Java로 피보나치 수열을 구현해보세요

1) 먼저 첫번째 방법은 간단하게 재귀로 구현할 수 있습니다.

public class Main {

  public static int count = 0;

  public static void main(String args[]) {
    int n = 10;

    System.out.println(fibonacci(n));
    System.out.println("메소드 실행횟수:" + count);
  }

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

output > 55
output > 메소드 실행횟수: 177

• 시간복잡도 O(2^2/n)
• 공간복잡도 O(2^2/n)

결과는 55로 정답입니다. 하지만 이 방법은 fibonacci 메소드가 무려 177번 실행됩니다. 만약 n값이 더 커지게 되면 함수 호출이 더 많아져서 제한된 Stack size를 넘을 수 있는 문제가 발생합니다.

Stack의 깊이가 증가하지 않게 하려면 어떻게 해야할까?

• 아예 Stack을 쓰지 말자. 즉 함수를 호출하지 말자.
• Stack을 쓰되 새로 추가해서 누적시키지 말고 있는걸 재사용하자 (Tail recursion)

2) 아예 Stack을 쓰지 않고 반복문으로 구하는 방법

public class Main {

  public static int count = 0;

  public static void main(String args[]) {
    int n = 10;

    System.out.println(fibonacci(n));
    System.out.println("메소드 실행횟수:" + count);
  }

  public static int fibonacci(int n) {
    int currentFibo = 0;
    int previousFibo = 1;
    int previousPreviousFibo = 0;
    if (n < 2) {
      return n;
    }
    for (int i = 2; i <= n; i++) {
      currentFibo = previousFibo + previousPreviousFibo;
      previousPreviousFibo = previousFibo;
      previousFibo = currentFibo;
    }
    return currentFibo;
  }
}

output > 55
output > 메소드 실행횟수: 1

• 시간복잡도 O(n)
• 공간복잡도 O(1)

이 방법으로는 당연히 재귀함수를 사용하지 않았기 때문에 Stack size에 대한 문제는 없습니다.

3) 꼬리 재귀함수를 사용해서 구현해보세요

우선 꼬리재귀란 return 으로 함수를 실행할 때 돌아올 곳을 저장하지 않고 자기 자리로 돌아와 반환받은 값만 돌려주는 방식입니다.

public class Main {

  public static int count = 0;

  public static void main(String args[]) {
    int n = 10;

    System.out.println(fibonacci(10,1,0));
    System.out.println("메소드 실행수:" + count);
  }

  public static int fibonacci(int n, int previousFibo, int previousPreviousFibo) {
    count++;

    int currentFibo = 0;
    if (n < 2) {
      return previousFibo;
    }

    // 이번 호출의 피보나치 수를 구하고
    currentFibo = previousFibo + previousPreviousFibo;
    // 다음번 재귀 호출을 위해 앞의 피보나치 수를 앞의앞의 피보나치 수로 한 칸 미루고
    previousPreviousFibo = previousFibo;
    // 다음번 재귀 호출을 위해 현재의 피보나치 수를 앞의 피보나치 수로 한 칸 미룬다.
    previousFibo = currentFibo;

    return fibonacci(n - 1, previousFibo, previousPreviousFibo);
  }
}
//결과적으로 파라미터 n은 반복하는 횟수의 index역할을 하고, previousFibo는 마지막에 currentFibo가 되므로 마지막 반환값이 previousFibo가 되게 된다. (for문과 로직이 동일하다)

output > 55
output > 메소드 실행횟수: 10

• 시간복잡도 O(n)
• 공간복잡도 O(1) 이지만 이 방법으로는 Java에서 Tail Call을 제대로 사용할 수 없습니다.

이 방법으로 메소드 실행횟수를 줄일 수 있습니다. 하지만 n의 값을 100000으로 올리면 Stack Size에러가 발생합니다. 이유는 Java 8 컴파일러 레벨에서 Tail-Call Optimisation(TCO)를 지원하지 않습니다. 하지만 Java8의 람다 표현식과 함수형 인터페이스로 구현할 수 있는 방법을 찾았습니다.
https://blog.knoldus.com/tail-recursion-in-java-8/

3. 마무리

JAVA에서 3가지 방법중 가장 적절한 방법으로는 반복문을 사용하는 2번 방법이 가장 적절한 것 같고
재귀는 언제봐도 항상 복잡한 것 같습니다.

+추가, 잘 이해했는지 복습문제로 n부터 1까지의 합을 구하는 프로그램도 만들어 보면 좋을 것 같습니다.

public class Main {

  public static int count = 0;

  public static void main(String args[]) {
    int n = 10;
    System.out.println(sum(n));
    System.out.println(sum1(n));
    System.out.println(sum2(n,1));
  }

  public static int sum(int n) {
    if(n == 1){
      return n;
    }
    return n + sum(n-1);
  }

  public static int sum1(int n) {
    int result = 0;
    for (int i = 1 ; i <= n; i++){
      result = result + i;
    }

    return result;
  }

  public static int sum2(int n, int result){
    if(n == 1){
      return result;
    }
    result = result + n;
    return sum2(n-1,result);
  }
}