差距在这:
线性递归:计算到头之后还要再回溯一遍 (相当于运算了两遍)
尾递归 :计算到头就得到结果,不回溯 (就运算一遍)
看代码,简单求阶乘公式:
线性递归:
// Line recursion 线性递归 public int line(int n) { if (n == 1) { return 1; } return n * line(n - 1); }
尾递归:
// Tail recursion 尾递归 public int tail(int n, int a) { return (n == 1) ? a : tail(n - 1, a * n); }
junit测试:ps>不要钻牛角尖告诉我超过long型上限为负
public void test() throws Exception { Assert.assertEquals(362880, line(9)); Assert.assertEquals(362880, tail(9,1)); Log.e("test", "line:" + line(9)); Log.e("test", "tail:" + tail(9, 1)); }
控制台输出:
其实递归思想很有艺术,简约而不简单.....
原文：http://www.cnblogs.com/andlp/p/5148805.html