尾递归与尾递归优化

关于递归：

• 递归是什么：递归，简单的说就是函数调用其自身。
• 如何递归：（1）在函数里调用自身。 （2）设定递归出口，也就是递归终止条件。
• 递归是如何执行的：函数执行时会把数据存入栈中，执行完后出栈，调用子函数的话，就把子函数数据入栈，等子函数执行完出栈，回到父函数执行，执行完再出栈，以此类推。因此，递归深度其实就是使用栈的深度。
• 递归的缺点：就是栈的问题，很可能因为递归过深，造成栈溢出。

关于尾递归：

• 百科解释：如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。
• 这个解释感觉有点看不懂，因为平时都是把return写末尾啊。但明显那不是尾递归。
• 百科解释：当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。
• 有点似懂非懂，是不是尾递归就是return时只有函数本身呢，比如 return f(x);。返回值不属于表达式一部分，排除 return f(x)+1;这种函数。

个人理解：尾递归重点在于递归时，函数除了返回递归函数的值，别的都是是执行完毕的。即除了返回子函数的返回值，没有多余的操作。

换个方式讲述：其实递归是可以理解为一颗树，即递归树。我们以斐波那契数列为例。

1	int Fib(int n){

2

3	if(n<=1) return n;//终止递归的条件

4

5	else return Fib(n-1)+Fib(n-2);//递归步骤

6

7

}

 

这个代码的递归树是这样的，这是典型的树形结构。箭头标记了执行的方向。

可以发现有两个特点：（1）这是树形结构，有分叉。（2）每次箭头执行到叶子节点后，总要返回回来（回溯）。

         

但其实最重要的是回溯，因为分叉造成回溯，尾递归的关键就是回溯。如果我们去掉分叉，那么就变成了左上方的图。如果我们去掉回溯，就变成右上方的图。

可以认为右上方的图就是一个尾递归。去掉返回的箭头并不是代表它不回溯，而是说明回溯是没有必要的，因为它回溯时除了返回值没做什么多余的事情。（尾递归优化可以认为是去掉了这个回溯，正常的执行是有回溯的）

尾递归最重要的特点：回溯时除了返回调用的函数的返回值没做别的事。

 如何设计尾递归：

1. 尾递归的递归树不能有分叉，即递归树必然是条链，有分叉就意味着回溯时有必要的操作。
2. 让回溯时没有多余的操作。（最重要的就是这个）

关于尾递归的优化：

对于优化。我们先回到栈，为什么回溯要用到栈。栈是用来存储函数执行所需的数据。如果我们递归调用后，不需要当前函数的数据呢？是不是就没必要存储这些信息了（就好像去掉了那个回溯的箭头）。

所以有些编译器对尾递归进行了优化，即递归调用时，不让函数数据新入栈，而是直接替换栈中当前函数的数据。这就实现了尾递归的优化。

转载请注明：旅途@KryptosX » 尾递归与尾递归优化