斐波那契数列——尾递归

来源于cs61B, Spring 2018, Discussion: Introduction to Java

斐波那契数列(Fibonacci Numbers)

比较简单直白的是递归方法：

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

这种方法属于树形递归(tree recursive)，因为它在代码主体内不止一次调用了自己。这种方法是相当insufficient的，因为它的分支因素导致了额外的开销。

比如fib(n-1)将会调用fib(n-2)和fib(n-3)，这样我们就调用了两次fib(n-2)，三次fib(n-4)。实际上我们根本无需调用多次。

因此我们引入了尾递归(tail-recursive)方法：
$$
fib2(n,k,f0,f1) 是N^{th}斐波那契数，给定f0是k-1^{th}和k^{th}的斐波那契数,\1<k<n。因此，fib2(n,1,0,1)就是简单的N^{th}的斐波那契数。
$$

public static int fib2(int n, int k, int f0, int f1) {
        if (k == n) {
            return f1;
        }
        return fib2(n, k+1, f1, f0+f1);
    }

在尾递归中，我们不需要重新计算已经知道的值。