什么是尾遞歸

Tail Recursion /te?l r??k??r?n/

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don’t get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of (return (recursive-function params)). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

示例一 : 累加

Consider a simple function that adds the first N integers. (e.g. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) {if (x === 1) {return x;} else {return x + recsum(x - 1);}
}

If you called recsum(5), this is what the JavaScript interpreter would evaluate:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

Here’s a tail-recursive version of the same function:

function tailrecsum(x, running_total = 0) {if (x === 0) {return running_total;} else {return tailrecsum(x - 1, running_total + x);}
}

Here’s the sequence of events that would occur if you called tailrecsum(5), (which would effectively be tailrecsum(5, 0), because of the default second argument).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

示例二 : 斐波那契數列##

在數學上，斐波那契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。

換成Java代碼如下：

public static long classicFibonacci(long num) {if(num <= 0) {return 0;}else if(num == 1 || num == 2) {return 1;}else {return classicFibonacci(num - 1) + classicFibonacci(num - 2);}
}

用尾遞歸方法改造一下

public static long tailRecursionFibonacci(long num) {if(num <= 0) {return 0;}else if(num == 1 || num == 2) {return 1;}else {return tailRecursionFibonacci(num, 1, 1, 2);}
}public static long tailRecursionFibonacci(long num, long first, long second, long index) {if(num == index) {return second;}else {return tailRecursionFibonacci(num, second, first + second, index + 1);//尾遞歸調用}
}

為什么需要尾遞歸

因為性能。

The consequence of tail recursion is that once you are ready to perform your next recursive step, you don’t need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step.

那么，我們不妨測試一下示例二：斐波那契數列中兩種算法。測試方法是用兩種算法得出斐波那契數列的第46項是多少且分別消耗多長時間。

首先，用classicFibonacci計算得出斐波那契數列的第46項。

@Test
public void testClassicFibonacci() {System.out.println(classicFibonacci(46));
}

運行結果如下

斐波那契數列的第46項是1836311903，用classicFibonacci得出斐波那契數列的第46項所消耗的時間是43.026秒

---

接著，用有尾遞歸方式的tailRecursionFibonacci計算得出斐波那契數列的第46項。

@Test
public void testTailRecursionFibonacci() {System.out.println(tailRecursionFibonacci(46));
}

斐波那契數列的第46項是1836311903，跟classicFibonacci的一致。用有尾遞歸方式的tailRecursionFibonacci得出斐波那契數列的第46項所消耗的時間是0.035秒，是classicFibonacci的1229倍，差距懸殊。

如果繼續用classicFibonacci得出斐波那契數列第n項（n>46），將消耗更長時間，甚至天荒地老也沒有算完。

參考資料

1. What is tail recursion?
2. 斐波那契數列