尾递归

递归

在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。
例如:

1
2
3
4
5
6
7
8
9
//计算num+(num-1)+(num-2)+...
public int decrease(int num)
{
if (num == 0)
{
return 0;
}
return decrease(num - 1) + num;
}

如果num比较小,代码是没有问题,但是如果num比较大递归比较深的话,就会栈溢出:java.lang.StackOverflowError
原因是因为decrease函数调用自身,然后再加上num,此时的需要等待decrease调用完成才能完成加法,也就是必须等到最后一个计算完,才能一个一个的返回,因此需要递归到最后一个函数完成时才能一个一个释放函数,所以当递归比较深的话,就会栈溢出。

尾递归

尾递归是在函数最后调用自身,每次调用完成后执行下次调用,不用存储函数状态,所以也不会有栈溢出。

1
2
3
4
5
6
7
8
9
public static int decrease(int num, int total)
{
if (num == 0)
{
return total;
}

return decrease(num-1,total + num);
}

坚持原创技术分享,您的支持将鼓励我继续创作!
显示 Gitment 评论