打印斐波那契数的递归调用

Question

如何打印斐波那契递归调用的结果，使输出如下所示

记录结果为 Fib(1) 为：1 Fib(0) 为：0 Fib(2) 为：1 Fib(1) 为：1 Fib(3) 为：2 Fib(1) 为：1 Fib(0) 为：0 Fib(2) 为：1 Fib(4) 为：3 Fib(1) 为：1 Fib(0) 为：0 Fib(2) 为：1 Fib(1) 为：1 Fib(3) 为：2 Fib(5) 为：5

这是我的代码

public class Test {
   public static void main(String[] args) {

      Fibonacci fib = new Fibonacci();
      System.out.println("Rec results is ");
      fib.recFib(5);

   }
}

class Fibonacci {
   
     //Your code starts here
      public int recFib(int n){
         
         if(n <= 1) {
            return n;
         }
         else {
            int result = recFib(n -1) + recFib(n-2);
            //System.out.println("Fib("+ n +") is: "+ result);
            return recFib(n -1) + recFib(n-2);
         }
      }
   // your code ends here

}

我尝试将打印语句放在不同的位置，但始终无法获得正确的输出。这不是一个家庭作业问题，而是课堂课程的一部分，所以希望你们能帮助我更好地理解它。我相信你只能使用一个打印语句。

Answer 1

如果将

print

语句从

if-else

中提取出来，那么将先进行递归调用，然后再打印（因此，您将在打印

n-1

的结果之前打印

n-2

和

n

的结果） 。这样你就得到了想要的结果。

class Fibonacci {

    //Your code starts here
    public int recFib(int n) {
        int result;
        if (n <= 1) {
            result = n;
        } else {
            result = recFib(n - 1) + recFib(n - 2);
        }
        System.out.println("Fib(" + n + ") is: " + result);
        return result;
    }
    // your code ends here
}

这会导致

Rec results is 
Fib(1) is: 1
Fib(0) is: 0
Fib(2) is: 1
Fib(1) is: 1
Fib(3) is: 2
Fib(1) is: 1
Fib(0) is: 0
Fib(2) is: 1
Fib(4) is: 3
Fib(1) is: 1
Fib(0) is: 0
Fib(2) is: 1
Fib(1) is: 1
Fib(3) is: 2
Fib(5) is: 5

祝上课顺利！