递归、调用栈及尾递归

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 的三种含义