具有 3 种不同递归方法的斐波那契数列

Question

我试图更好地理解 Java 的递归，我正在做一个使用迭代的程序，头和尾 recursion.It 应该计算不同方法调用了多少次。我应该在头部和尾部添加什么来完成程序？提前谢谢你

public class Recursion {
    public static void main(String[] args) {
        System.out.println("Test fibonacci: 0 = 0");
        System.out.println("iterativ: " + fibIt(0));
        System.out.println("head: " + fibHr(0));
        System.out.println("tail: " + fibTr(0));

        System.out.println("\nTest fibonacci: 5 = 5");
        System.out.println("iterativ: " + fibIt(5));
        System.out.println("head: " + fibHr(5));
        System.out.println("tail: " + fibTr(5));

        System.out.println("\nTest fibonacci: 10 = 55");
        System.out.println("iterativ: " + fibIt(10));
        System.out.println("head: " + fibHr(10));
        System.out.println("tail: " + fibTr(10));
    }

    private static int fibIt(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
                return 1;
        }

        int a = 0;
        int b = 1;

        for (int i = 2; i <= n; i++) {
            b = a + b;
            a = b - a;
        }

        return b;
    }

    private static int fibHr(int n) {
        int counter = 0;
        switch (n) {
            case 0:
                counter +=1;
                return 0; 
            case 1:
                counter += 1;
                return 1;
            default:
                counter = counter +1;
                return fibHr(n - 1) + fibHr(n - 2) ;    
        }
    }

    private static int fibTr(int n) {
        return fibTr(0, 1, n);
    }

    private static int fibTr(int a, int b, int n) {
        switch (n) {
            case 0:
                return a;
            case 1:
                return b;
            default:
                return fibTr(b, a + b, n - 1);
        }
    }    
}

如何在头部递归中获取计数器值？我已经尝试了所有方法来打印出来，但我不知道它是如何工作的。我想数一数 returns 我试过 System.out.print 但我只是得到了大量的 1-s.

Answer 1

您可以将每个方法转换为 class 的实例方法，然后将计数器保存在私有字段中，并使用 getter 公开值。

public class HeadRecursion {
  private long counter = 0;
  public int fib(int n) {
    ++counter;
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fibHr(n - 1) + fibHr(n - 2);
    }
  }
  public long getCounter() { return count; }
}

然后你可以实例化你的class，运行你的函数然后得到并输出计数器：

public static void main() {
  final var obj = new HeadRecursion();
  final var number = obj.fib(10);
  System.out.println(number);
  System.out.println(obj.getCounter());
}

请注意，counter 必须是在 class 中声明的字段，并且不是方法内部定义的局部变量，原因至少有两个:

局部变量在其范围之外不可见也不可访问，即封闭函数
每次调用该函数时，变量将为 re-initialized。每次递归调用都会再次从变量的原始值开始。

具有 3 种不同递归方法的斐波那契数列

Fibonacci with 3 different recursion methods

java

fibonacci