递归与尾递归简析
与之相对的是非尾递归函数，你先执行递归调用，然后获取递归调用的结果进行计算, 这样你需要先获取每次递归调用的结果，才能获取最后的计算结果。看下面计算n阶乘的函数，它是一个非尾递归函数。我们发现cal(n-1)返回的值被cal(n)使用，因此对cal(n-1)的调用并不是cal(n)所做的最后一步。
public class NonTailRecursiveTest {
public static int cal(int n) {
if (n == 0) return 1;
return n * cal(n - 1);
}
public static void main(String[] args) {
System.out.println(cal(6));
}
}结果：
cal(6)
6*cal(6-1)
6*5*cal(5-1)
6*5*4*cal(4-1)
6*5*4*3*cal(3-1)
6*5*4*3*2*cal(2-1)
6*5*4*3*2*1
720通常认为尾递归函数优于非尾部递归函数，编译器优化尾部递归函数的思想很简单，因为递归调用是最后一条statement，所以在当前函数中没有什么可做的，这样没有必要保存当前函数的堆栈结构了。而非尾递归函数调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。
一个non-tail递归函数可以优化成尾递归函数吗?我们还是以n阶乘为例，其方法是再使用一个参数，并在第二个参数中累积阶乘值。当n达到0时，返回累积值。看如下方法：
public class TailRecursiveTest {
//一个尾递归函数
public static int calTR(int n, int a) {
if (n == 0)
return a;
return calTR(n - 1, n * a);
}
// A wrapper over calTR
public static int cal(int n) {
return calTR(n, 1);
}
// Driver code
public void main(String[] args) {
System.out.println(cal(6));
}
}calTR(6,1)
calTR(5,6)
calTR(4,30)
calTR(3,120)
calTR(2,360)
calTR(1,720)
calTR(0,720)
720本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-02-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读