1.递归与栈
无论是否递归调用，当在一个函数(外层函数)的运行期间调用另一个函数（被调用函数，即内层函数）时，在运行被调用函数之前，系统需要先完成3个操作，即：
- 将所有的实参、返回地址等信息传递给被调函数保存；
- 为被调函数的局部变量分配存储区；
- 将控制转移到被调函数的入口。
从被调函数返回调用函数（外层函数）之前，系统还要完成3个操作，即：
- 保存被调函数的计算结果；
- 释放被调函数的数据区；
- 依照被调函数保存的地址将控制权转移到调用函数（外层函数）。
当有多个函数构成嵌套调用时，按照"后调用先返回"的原则，上述函数之间的信息传递和控制转移必须通过"栈"来实现，每当调用一个函数时，就在栈顶为它分配一个存储区，每当退出一个函数时，就释放它的存储区，当前正在运行的函数的数据区必在栈顶。递归函数的运行过程类似于多个函数的嵌套调用，只是调用和被调用函数是同一个函数。
函数调用时，需要在栈中分配新的帧，将返回地址，调用参数和局部变量入栈。所以递归调用越深，占用的栈空间越多。
假设n = 3，该递归的执行步骤，即圧栈、出栈的说明如下：
function recursive(int n) {
if(n == 1) return 1;
doSomething();
recursive(n-1);
doOtherThing();
}
递归与调用栈
2.尾递归
为了解决递归的开销大问题，使用尾递归优化，具体分两步：
1）编码时，把递归调用的形式写成尾递归的形式；
2）编译时，编译器碰到尾递归，自动按照某种特定的方式进行优化编译
使用尾递归的好处：因为进入下一层函数不再需要参考外层函数的信息，因此没必要保存外层函数的栈信息，递归需要用的stack只有目前这层被调用函数的，因此避免了栈溢出风险。
一些语言提供了尾递归优化特性，当识别出使用了尾递归时，会相应地只保留当前层函数的stack，节省内存，不会发生stackOverflowException调用栈溢出。
注意：
JVM缺乏尾调用指令,java编译器对尾递归的优化未实现，所以在java中尽量避免过深的递归调用，如果需要使用递归，建议优化成迭代式。*
function story() {
从前有座山，
山上有座庙，
庙里有个老和尚，
一天老和尚对小和尚讲故事：
story() // 尾递归，进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。
}
/**
* 尾递归的精髓在于往内进行下一层解析的时候，这一层函数执行完了,不再需要在保留出栈时需要从当前
的执行到的行、相关变量值继续的信息。所以空间复杂度是O(1)。
*/
function story() {
从前有座山，
山上有座庙，
庙里有个老和尚，
一天老和尚对小和尚讲故事：
story()，
小和尚听了，
找了块豆腐撞死了 // 非尾递归，下一个函数结束以后此函数还有后续，
//所以必须保存本身的环境以供处理返回值。
}
尾递归就是操作的最后一步是调用自身的递归。注意，尾递归的判断标准是函数运行 最后一步 是否调用自身，而不是是否在函数的最后一行调用自身。
这个不是尾递归：
function fibonacci(n) {
...
if (n === 1) return 1;
...
return n * fibonacci(n-1); // 最后一步是乘法运算，而不是调用自身，因此不是尾递归
}
这个是尾递归：
function fibonacci(n,m,result) {
...
if (n === 1) return 1;
...
return fibonacci(n,n-1,n*(n-1));
}
3.二叉树遍历中的两次递归示例
/**
* 10
* / \
* 6 14
* / \ / \
* 5 8 12 19
* / \ \
* 4 9 11
*
*/
public void preOrderVisit(Node n){
//退出递归的条件：到达叶子节点
if(n == null) return;
System.out.println("<前序>--左/右子树圧栈--当前节点值 ---> " + n.value);
/**递归，实际是圧栈过程，可以理解为分两个过程执行：
step1：递归嵌套过程（圧栈过程，圧栈时记录当前函数执行状态，包括当前执行
到哪行、当前局部变量值等，传递给被调用函数（自己）），即调用自身
的过程，圧栈时在递归调用前的每一行代码都被执行，递归调用后面的代
码不能到达执行（递归处可理解为while(true)循环）。一直到达左侧遍
历递归终止条件。
类似while true循环，连续输出10 6 5 4
*/
preOrderVisit(n.left); //4:无下一个左子节点，执行下一行命令
//此处左子树函数站开始出栈，4已出栈，从5开始回溯到根节点，回溯过程执行的是递归命令后面的代码行
System.out.println("<中序>--左子树出栈--当前节点值--->" + n.value);//左子树结束递归嵌套后执行该行
//当前是节点4,输出中序4
preOrderVisit(n.right);//转入执行该递归嵌套。后续左子树每一次出栈都进入右子树递归，转进右子树的入栈、出栈过程，4无右子树，未进入递归圧栈过程，执行下一行
System.out.println("<后序>--右子树出栈--当前节点值--->" + n.value);//输出后续4
}
参考:
[1].什么是尾递归
[2].尾调用优化
[3].栈是如何实现递归的:递归与栈一些不得不说的事
[4].stack 的三种含义
网友评论