### 大纲

源于生活

假设你正在一个电影院，你想知道自己坐在哪一排，但是前面人很多，你懒得去数了，于是你问前一排的人「你坐在哪一排？」，假如前面的人(叫狗蛋) 回答你以后，只要把狗蛋的答案加一，就是自己所在的排了。不料狗蛋比你还要懒，他也不想数，于是他也问前面的铁柱坐哪一排？ 这样狗蛋用和你一样的步骤知道了自己所在的排数。然后铁柱也跟着学呀，直到他们这一串人问到了最前面的一排，第一排的人告诉问问题的人 我在第一排。最后大家就都知道自己在哪一排了。

上面生动展示递归的过程，可能大部分同学们包括我在大一的时候，在上数据结构的课就和它有了不解之缘，不过，我敢打包票很多人以及初学者刚开始接触递归的时候，是一脸懵的，我也是，给我的感觉就是，递归太强了 就好像链式反应一样。可能一大部分人知道递归，也能看的懂递归，但在实际做题过程中，却无从下口，有时候还容易被递归给搞晕。身边也有好几个我的同学问我来有没有快速掌握递归的捷径,哈哈,不可能的哈,跟着俺的节奏读下去。

1 需要知道的三个要点

首先你想让函数干啥

而这是你说了算的，换句话说，我们先不管函数里面的代码什么，而是要想明白，你这个函数是用来干啥的。

譬如，俺定义了一个函数

 ​
 // 算 m 的阶乘(假设m不是0)
 int k(int m){
 ​
 }
 ​

这个函数的功能是算 m 的阶乘。ok，我们已经定义了一个函数，并且晓得了它的功能是干啥的，接下来我们瞧瞧要点二。

然后结束条件在哪里呢

所谓递归，它就是在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，那就进入无底洞。也就是说，我们需要找出当参数是什么东西，递归才结束，之后直接把结果返回，但是请你注意了，这个时候我们必须能根据这个参数的值，能够很直接知道函数的结果是什么。譬如，上面那个例子中，当 m = 1 时，那你应该能够直接知道 f(m) 是啥吧？就不写了，把要点二加进代码里面，如下

 ​
 // 算 m 的阶乘(假设m不是0)
 int f(int m){
     if(m == 1){
         return 1;
     }
 }
 ​

哪有人就说了 m=2 我也知道是几呀？ 也行，只要你觉得参数合适，你能够直接知道函数的结果，那么你就可以把这个参数作为结束的条件，代码我也写一下

 ​
 // 算 m 的阶乘(假设m>=2)
 int f(int m){
     if(m == 2){
         return 2;
     }
 }
 ​

你觉得是不是可以了呀？ 那m=3,m=4，因为这个 m = 1时候，会被漏掉，真的是捡了西瓜丢了芝麻，当 m <= 2时，f(m) = m，所以为了更加严谨点，咱写成这样：

 ​
 // 算 n 的阶乘(假设n不是0)
 int f(int m){
     if(m <= 2){
         return m;
     }
 }
 ​

最后是这函数的等价关系

我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。譬如，f(n) 这个范围比较大，我们可以让 f(n)=n * f(n-1)。这样，范围就由 n 变成了 n-1 了，范围变小了，并且为了原函数 f(n) 不变，我们需要让 f(n-1) 乘以 n。说白了，就是要找到原函数的一个等价关系式子，f(n)的等价关系式为 n * f(n-1)，即f(n) = n * f(n-1)。 这个等价关系式的寻找，可以说是最难的一步了，如果你不大懂也没关系，因为你又不是神童，我们还需要多接触几道题，我会在接下来，找几道递归题，让你慢慢熟悉起来。想在找出了这个等价式，继续完善我们的代码，我们把这个等价式写到函数里。如下：

 ​
 // 算 m 的阶乘(假设m不为0)
 int f(int m){
     if(m <= 2){
         return m;
     }
     // 把 f(m) 的等价操作写进去
     return f(m-1) * m;
 }
 ​

2 两种递归模型（分类）

模型一： 在递去的过程中解决问题

 ​
 function recursion(大规模){
   if (end_condition){   // 明确的递归条件
       end;
   }else{
       solve;            // 递去
       recursion(小规模); // 遇到最深处，不断地归来
   }
 }
 ​

模型二：在归来的过程中解决问题

 ​
 function recursion(大规模){
     if (end_condition){  // 明确的递归条件
         end;  
     }else{  // 先把问题全部展开描述，再由尽头“返回”每次解决没不中剩余的问题
         recursion(小规模);  // 递去
         solve;             // 归来    
     }
 }
 ​

3 你什么时候考虑递归

具有以下特征的问题考虑递归求解：

• 当问题和子问题具有递推关系，譬如杨辉三角，计算阶乘。

• 具有递归性质的数据结构，譬如链表，树，图。

• 反向性问题，比如取反。 .......

4 应用场景在哪里

在我们实际学习工作中，递归一般用在解决三类问题上：

　　 (1). 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；

　　 (2). 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；

　　 (3). 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

就是一句话，你的问题是不是能通过层层拆解到最小粒度来求解。

和循环有关系？

是两种不同解决问的思路，递归是很直白地描述一个问题的解题过程，也是我们最容易想到的。循环和递归都有共同的特性，就是重复做任务，有时候使用循环可能不会清晰地描述问题的解决步骤。单从算法设计上看，递归和循环并无优劣之别。然而，在实际开发中，因为函数调用的开销，递归常常会带来性能问题，特别是在求解规模不确定的情况下；而循环因为没有函数调用开销，所以效率会比递归高。 递归求解方式和循环求解方式往往可以互换，也就是说，如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成循环往往是好的。问题的递归实现转换成非递归实现一般需要两步工作：

• 1）自己开辟堆栈（一些局部变量）来保存这些内容便于来替代系统栈，譬如树的三种非遍历方式（后面会讲到）；

• 2） 把对递归的调用转变为对循环处理。特别地，在下文中我们将给出递归算法的一些经典应用案例，对于这些案例的实现，我们一般会给出递归和非递归的解法，方便你体会。

5 递推本质

帕斯卡三角形是排列成三角形的一系列数字。也就是有所耳闻的杨辉三角。 在帕斯卡三角形中，每一行的最左边和最右边的数字总是 1。 对于其余的每个数字都是前一行中直接位于它上面的两个数字之和。

下面的插图给出了一个 5 行的帕斯卡三角：

这就是个具有具体行数的帕斯卡三角形。

递推关系

让我们从帕斯卡三角形内的递推关系开始。

首先，我们定义一个函数 f(m,q)，它将会返回帕斯卡三角形第 m 行、第 q 列的数字。

我们可以使用下面的公式来表示这一递推关系：

f(m,q)=f(m−1,q−1)+f(m−1,q)

基本情况

可以看到，每行的最左边和最右边的数字是基本情况，在这个问题中，它总是等于 1；

因此，我们可以将基本情况定义如下:

f(m,q)=1 where q=1 or m=q

演示

正如我们所看到的，一旦知道了递推关系 和 基本情况，递归函数的实现变得更加直观，特别是在我们用数学表达式表示出这两个元素之后。

下面给出一个例子，展示我们如何用这个公式递归地计算 f(5,3), 也就是 帕斯卡三角形第 5 行中的第 3 个数。

可以将 f(5,3) 分解为 f(5,3)=f(4,2)+f(4,3)，然后递归地调用f(4,2) 和 f(4,3)：

对于调用的 f(4,2)，我们可以进一步展开它，直到到达基本情况，正如下面描述的： f(4,2)=f(3,1)+f(3,2)=f(3,1)+(f(2,1)+f(2,2))=1+(1+1)=3

对于调用的 f(4,3)，类似地，我们可以将其分解为： f(4,3)=f(3,2)+f(3,3)=(f(2,1)+f(2,2))+f(3,3)=(1+1)+1=3

最后，我们结合上述子问题的结果： f(5,3)=f(4,2)+f(4,3)=3+3=6

您可能已经注意到递归解决方案可能会导致一些重复的计算，譬如，我们重复计算相同的中间数以获得最后一行中的数字。 假如为了得到 f(5,3) 的结果，我们在 f(4,2) 和 f(4,3)的调用中计算了 f(3,2) 两次，这样重复计算效率肯定不高，下一节我们会给出优化方案来避免重复计算（即记忆术）。

6 复杂性分析

6.1 递归时间复杂度计算

给出一个递归算法，其时间复杂度 O(T) 通常是递归调用的数量（记作 R） 和计算的时间复杂度的乘积（表示为 O(s)）的乘积：

O(T)=R∗O(s)

举例

在反转字符串问题中，我们需要以相反的顺序打印字符串，其递归关系可以表示如下：

printReverse(str) = printReverse(str[1...n]) + print(str[0])

其中 str[1...n] 是输入字符串str 的子串，不包含前导字符 str[0]。

如您所见，该函数将被递归调用 n 次，其中 n 是输入字符串的大小。在每次递归结束，我们只打印前导字符，所以该特定操作的时间复杂度是不变的，即 O(1)。

总而言之，我们的递归函数 printReverse(str) 的总体时间复杂度为

O(printReverse)=n∗O(1)=O(n)。

执行树分析递归调用数量

在分析递归的时间复杂度时，递归调用的数量不一定和N成线性关系，比如斐波那契数，其递推关系已经被定义为f(n) = f(n-1) + f(n-2)。乍一看，在执行斐波那契函数期间计算递归调用的数量似乎并不简单。

执行树定义

执行树是一个用于表示递归函数的执行流程的树。树中的每个节点都表示递归函数的调用。因此，树中的节点总数对应于执行期间的递归调用的数量。 递归函数的执行树将形成 n叉树，其中 n 作为递推关系中出现递归的次数。例如，斐波那契函数的执行将形成二叉树，下面的图示展现了用于计算斐波纳契数 f(4) 的执行树。

在 n 层的完全二叉树中，节点的总数为 2n−1。所以 f(n) 中递归数目的上限也是 2n−1。那么我们可以估计 f(n) 的时间复杂度为O(2n) 。

6.2 递归空间复杂性分析

在计算递归算法的空间复杂度时，应该考虑造成空间消耗的两个部分：递归相关空间（recursion related space）和非递归相关空间（non-recursion related space）。

递归相关空间

递归相关空间是指由递归直接引起的内存开销,它是用于跟踪递归函数调用的堆栈。为了完成函数调用，系统应该在栈中分配一些空间来保存三个重要信息：

• 函数调用的返回地址。一旦函数调用完成，程序应该知道返回的位置，即函数调用之前的点。

• 传递给函数调用的参数。

• 函数调用中的局部变量。

栈中的这个空间是函数调用期间产生的最小成本。然而，一旦完成函数调用，就会释放该空间。

对于递归算法，函数调用将连续链接直到它们到达基本情况。这意味着用于每个函数调用的空间也会累积。 那如果没有产生其他内存消耗，则此递归引起的空间将是算法的空间上限。

譬如，提到的反转字符串例子中，我们没有使用额外的内存，因为我们仅仅是打印一个字符。对于每个递归调用，我们假如它可能需要一个最大为某一常量值的空间。并且递归调用最多可以链接 n 次，其中 n 是输入字符串的大小。因此，该递归算法的空间复杂度就是 O(n)。

为了更好地说明这一点，接下来我们将会展示递归调用f(x1) -> f(x2) -> f(x3)的执行顺序以及栈空间的分配情况。

栈中的空间将会分配给 f(x1) 来调用 f(x2)。类似的情况也同样发生在 f(x2) 中，系统会给 f(x3) 的调用分配另外一个空间，最后在 f(x3) 中，我们到达基本情况，所以在 f(x3) 中没有进行下一步的递归调用。

由于这些与递归相关的空间消耗，有时可能会遇到称为堆栈溢出的情况，其中为程序分配的堆栈达到其最大空间限制并导致程序最终失败。在设计递归算法，应该仔细评估在输入规模扩大时是否存在堆栈溢出的可能性，栈溢出也是非常容易出错的点。

非递归相关空间

正如名称所示，非递归相关空间指的是与递归过程没有直接关系的内存空间，通常包括为全局变量分配的空间（在堆上）。

不管是否递归，你都可能需要在任何函数调用之前将问题的输入存储为全局变量。你可能还需要保存递归调用的中间结果。譬如，在这种递归算法解决斐波那契数问题时,我们使用映射（map）来跟踪在递归调用产生的所有中间斐波那契数。

7 递归的优化策略

记忆化定义

记忆化 是一种优化技术，可用于加快计算机程序的速度，方法是存储昂贵的函数调用的结果，并在相同的输入再次出现时返回缓存的结果。 (来源: 维基百科)

递归是一种直观而有效的实现算法的方法。 但是，如果我们不明智地使用它，可能会给性能带来一些不希望的损失，譬如重复计算。 在前面我们提到了帕斯卡三角的重复计算问题，其中一些中间结果被多次计算，记忆化可以用来避免这个问题。

回到斐波那契函数F(n)。 我们可以使用哈希表来跟踪每个以 n 为键的 F(n) 的结果。 散列表作为一个缓存，可以避免重复计算。 记忆化技术是一个很好的例子，它演示了如何通过增加额外的空间来减少计算时间。

为了便于比较，我们在下面提供了带有记忆化功能的斐波那契数列解决方案的实现。

作为一种练习，您可以尝试使记忆化更加通用和非侵入性，即应用记忆化技术而不改变原来的功能。

 ​
 import java.util.HashMap;
 ​
 public class Main {
 ​
   HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();
 ​
  private int fib(int N) {
  if (cache.containsKey(N)) {
  return cache.get(N);
     }
  int result;
  
  if (N < 2) {
       result = N;
     } else {
       result = fib(N-1) + fib(N-2);
     }
  // keep the result in cache.
     cache.put(N, result);
  return result;
   }
 }
 ​

通过记忆化，我们保存每个索引 n 对应的的斐波那契数的结果。我们确信每个斐波那契数的计算只会发生一次。而从递推关系来看，斐波纳契数 f(n) 取决于其所有 n-1 个先验斐波纳契数。结果，计算 f(n) 的递归将被调用 n-1 次以计算它所依赖的所有先验数字。

现在，我们可以计算一下采用了记忆化技术优化后的时间复杂度，即 O(1)∗n=O(n)。可以得出记忆化技术不仅可以优化算法的时间复杂度，还可以简化时间复杂度的计算。

尾递归

上一节我们讨论了递归空间复杂性分析话题，从中我们了解到递归调用在系统调用栈上会产生额外空间，如果递归调用层级很深，程序执行过程中很可能导致栈溢出。针对这种情况，有一种称为尾递归的特殊递归，它可以控制递归导致空间开销的影响。

尾递归定义

尾递归函数是递归函数的一种，其中递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。 尾递归的好处是，它可以避免递归调用期间栈空间开销的累积，因为系统可以为每个递归调用重用栈中的固定空间。可以理解为，在程序执行到递归函数最后一条递归调用指令时回收了当前的栈空间（其实复用了当前的栈空间），爽歪歪。

类别一：问题的定义是按递归定义的

斐波拉契数列

是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34...,即第一项f(1)=1, f(2)=1..., 第n项是 f(n)=f(n-1)+f(n-2), 它是求第n项的值是多少。

两种递归解法：经典解法和优化解法 两种非递归解法：递推法和数组法

public class FibonacciSequence {

    /**
     * @description 经典递归法求解
     * 
     * 斐波那契数列如下：
     * 
     *  1,1,2,3,5,8,13,21,34,...
     * 
     * *那么，计算fib(5)，需要计算1次fib(4),2次fib(3),3次fib(2)，调用了2次fib(1)*，即：
     * 
     *  fib(5) = fib(4) + fib(3)
     *  fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1)
     *  fib(3) = fib(2) + fib(1)
     *  
     * 这里面包含了许多重复计算，而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
     * 后面的optimizeFibonacci函数进行了优化，使时间复杂度降到了O(n).
     * 
     * @author Datalong
     * @created 2021年8月27日 下午13:00:42
     * @param n
     * @return
     */
    public static int fibonacci(int n) {
        if (n == 1 || n == 2) {     // 递归终止条件
            return 1;       // 简单情景
        }
        return fibonacci(n - 1) + fibonacci(n - 2); // 相同重复逻辑，缩小问题的规模
    }
    

对经典递归法的优化

/** * 斐波那契数列如下: 1,1,2,3,5,8,13,21,34,... 那么，我们可以这样看：fib(1,1,5) = fib(1,2,4) = fib(2,3,3) = 5 也就是说，以1,1开头的斐波那契数列的第五项正是以1,2开头的斐波那契数列的第四项， 而以1,2开头的斐波那契数列的第四项也正是以2,3开头的斐波那契数列的第三项， 更直接地，我们就可以一步到位：fib(2,3,3) = 2 + 3 = 5,计算结束。 注意，前两个参数是数列的开头两项，第三个参数是我们想求的以前两个参数开头的数列的第几项。

/* 时间复杂度：O(n)
*
* @author Datalong
* @param first 数列的第一项
* @param second 数列的第二项
* @param n 目标项
* @return
*/

public static int optimizeFibonacci(int first, int second, int n) {
          if (n > 0) {
              if(n > 0) {
                  return first;
              }else if(n == 2){   递归终止条件
                  return second;
              }else if(n == 3){   //递归终止条件
                return first + second;
          }
          return optimizeFibonacci(second, first + second, n-1);  //相同重复逻辑
    }
    return -1;
  }
  
--------------------------我是分割线------------------------------

/**
* @decription 非递归解法：有去无回
* @author Datalong
* @created 2021年8月27日 下午13:00:42 
* param n
* @return 
*/
public static fibonacci_loop(int n) {

    if (n == 1 || n == 2) {
        return 1;
    }
    
    int result = -1;
    int first = 1;   //自己维护的“栈”，以便状态回溯；
    int second = 1;  //自己维护的“栈”，以便状态回溯；
    
    for (int i = 3; i <= n; i++) { //循环
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}
  
----------------------我是分隔线-----------------------------

/**
* @description 使用数组存储斐波那契数列
* @author Datalong
* @param n
* @return
*/
public static int fibonacci_array(int n) {
        if (n > 0) {
            int[] arr = new int[n];         // 使用临时数组存储斐波纳契数列
            arr[0] = arr[1] = 1;

            for (int i = 2; i < n; i++) {   // 为临时数组赋值
                arr[i] = arr[i-1] + arr[i-2];
            }
            return arr[n - 1];
        }
        return -1;
    }
    

回文字符串的判断

题目描述：回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串 提供两种解法： 递归判断； 循环判断；

 * @author rico       
 */      
public class PalindromeString {

    /**     
     * @description 递归判断一个字符串是否是回文字符串
     * @author rico       
     * @created 2021年8月27日 下午5:45:50     
     * @param s
     * @return     
     */
    public static boolean isPalindromeString_recursive(String s){
        int start = 0;
        int end = s.length()-1;
        if(end > start){   // 递归终止条件:两个指针相向移动，当start超过end时，完成判断
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }else{
                // 递归调用，缩小问题的规模
                return isPalindromeString_recursive(s.substring(start+1).substring(0, end-1));
            }
        }
        return true;
    }

--------------------------------我是分割线-------------------------------------

    /**     
     * @description 循环判断回文字符串
     * @author rico       
     * @param s
     * @return     
     */
    public static boolean isPalindromeString_loop(String s){
        char[] str = s.toCharArray();
        int start = 0;
        int end = str.length-1;
        while(end > start){  // 循环终止条件:两个指针相向移动，当start超过end时，完成判断
            if(str[end] != str[start]){
                return false;
            }else{
                end --;
                start ++;
            }
        }
        return true;
    }
    

类别二：问题解法按递归算法实现

1) 汉诺塔问题

Description:古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。 有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下， 小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。

public class HanoiTower {

    /**     
     * @description 在程序中，我们把最上面的盘子称为第一个盘子，把最下面的盘子称为第N个盘子
     * @author rico       
     * @param level：盘子的个数
     * @param from 盘子的初始地址
     * @param inter 转移盘子时用于中转
     * @param to 盘子的目的地址
     */
    public static void moveDish(int level, char from, char inter, char to) {

        if (level == 1) { // 递归终止条件
            System.out.println("从" + from + " 移动盘子" + level + " 号到" + to);
        } else {
            // 递归调用：将level-1个盘子从from移到inter(不是一次性移动，每次只能移动一个盘子,其中to用于周转)
            moveDish(level - 1, from, to, inter); // 递归调用，缩小问题的规模
            // 将第level个盘子从A座移到C座
            System.out.println("从" + from + " 移动盘子" + level + " 号到" + to); 
            // 递归调用：将level-1个盘子从inter移到to,from 用于周转
            moveDish(level - 1, inter, from, to); // 递归调用，缩小问题的规模
        }
    }

    public static void main(String[] args) {
        int nDisks = 30;
        moveDish(nDisks, 'A', 'B', 'C');
    }
    

类别三：数据的结构是按递归定义的

1) 二叉树深度

/**
* Title: 递归求解二叉树的深度
* Description:
* @author rico
* @created 2021年8月27日 下午17:5:42 
*/

public class BinaryTreeDepth {

    /**     
     * @description 返回二叉数的深度
     * @author rico       
     * @param t
     * @return     
     */
    public static int getTreeDepth(Tree t) {

        // 树为空
        if (t == null) // 递归终止条件
            return 0;

        int left = getTreeDepth(t.left);  // 递归求左子树深度，缩小问题的规模
        int right = getTreeDepth(t.left); // 递归求右子树深度，缩小问题的规模

        return left > right ? left + 1 : right + 1;
    }
}

2) 三种遍历（递归）

/**
 * @description 前序遍历(递归)
 * @author rico
 * @created 2021年8月27日 下午13:15:43
 * @param root
 * @return
 */
 
前序遍历（递归）
 public String preOrder(Node<E> root) {
        StringBuilder sb = new StringBuilder(); // 存到递归调用栈
        if (root == null) {   // 递归终止条件
            return "";     // ji 
        }else { // 递归终止条件
            sb.append(root.data + " "); // 前序遍历当前结点
            sb.append(preOrder(root.left)); // 前序遍历左子树
            sb.append(preOrder(root.right)); // 前序遍历右子树
            return sb.toString();
        }       
    }


// 中序遍历，递归实现
template<class T>
void BST<T>::inorder(BSTNode<T>* p) 
{
    if (p != 0) 
    {
        inorder(p->m_left);
        visit(p);
        inorder(p->m_right);
    }
}
 
// 后序遍历，递归实现
template<class T>
void BST<T>::postorder(BSTNode<T>* p) 
{
    if (p != 0) 
    {
        postorder(p->m_left);
        postorder(p->m_right);
        visit(p);
    }
}

3）非递归遍历实现

4.1 前序遍历，非递归实现

起始将树根节点添加到栈中；栈弹出一个元素，访问该节点，并把该节点的右子节点和左子节点添加到栈中。说明，节点为空不能添加； 判断栈是否为空，为空树遍历结束，不为空继续添再加。

4.2 实例演示

4) 栈的变化过程

5) 编码实现

// 中序遍历，非递归栈实现

template<class T>
void BST<T>::iterativeInorder() 
{
    Stack<BSTNode<T>*> travStack;
    BSTNode<T>* p = root;
    while (p != nullptr) 
    {
        while (p != nullptr)
        {                 
            if (p->m_right)                
                travStack.push(p->m_right); 
 
            travStack.push(p);
            p = p->m_left;
        }
 
        p = travStack.pop();             
        while (!travStack.empty() && p->m_right == nullptr)
        { 
            visit(p);                                
            p = travStack.pop();
        }
 
        visit(p);                       
        if (!travStack.empty())          
            p = travStack.pop();
        else 
            p = nullptr;
    }
}
 
// 中序遍历，非递归栈实现

template<class T>
void BST<T>::iterativeInorder_2() 
{
    Stack<BSTNode<T>*> travStack;
    BSTNode<T>* p = root;
    while (p != nullptr) 
    {
        travStack.push(p);
        for (; p != nullptr && p->m_left != nullptr; p = p->m_left)
            travStack.push(p->m_left); 
 
        p = travStack.pop(); 
        visit(p);
        while (!travStack.empty() && p->m_right == nullptr)
        { 
            p = travStack.pop();
            visit(p);                                
        }
 
        p = p->m_right;
    }
}

6) 后序遍历，非递归栈实现

和中序遍历非递归栈实现比较类似，不同的是：

中序遍历弹出左节点之后，会继续弹出父节点，然后判断父节点是否有右节点，没有继续弹出下一个节点；有则以这个右节点进行下一次循环遍历。

后序遍历弹出左节点之后，继续弹出父节点，然后判断父节点是否有右节点，没有继续弹出下一个节点；有右节点且这个右节点之前已经访问过，继续弹出下一个节点；有右节点且这个右节点之前没有访问过，则以这个右节点为节点进行下一次循环遍历。

最主要的是需要理解当一个节点的右节点已经被访问了，则它的右节点不需要再被访问。

实现步骤

将树根节点赋值给变量 p，定义一个标记变量guard 将根节点赋值给它；循环判断 p 是否为空，非空执行循环； 循环中将 p节点 添加到栈中，访问 p节点 的左节点，非空就添加到栈中，继续访问 p节点 左节点的左节点非空就添加到栈中，直到左节点为空； 将p赋值给 guard，弹出栈顶元素将其赋值给 p，并访问该元素； 栈不为空且弹出的栈顶元素没有右节点或者有右节点但该右节点和 guard 相等（也就是右节点刚刚被访问过），继续弹出栈元素并访问它直到，栈为空或者弹出的节点有右节点且没有被访问； 将最后一个弹出的节点右节点赋值给p，回到步骤二，继续执行;

实例演示

栈的变化过程

说明：在栈变化过程中的第四个栈，栈顶是D，在对D节点右访问的时候，发现节点I已经被访问过，此时不需要访问D的右节点，直接输出D节点并弹出D节点即可。

7) 编码实现

// 后序遍历，非递归栈实现
template<class T>
void BST<T>::iterativePostorder() 
{
    Stack<BSTNode<T>*> travStack;
    BSTNode<T>* p = root, * guard = root;
    while (p != nullptr) 
    {
        for (; p->m_left != nullptr; p = p->m_left)
            travStack.push(p);
 
        while (p->m_right == nullptr || p->m_right == guard)
        {
            visit(p);
            if (travStack.empty())
                return;
 
            guard = p;
            p = travStack.pop();
        }
 
        travStack.push(p);
        p = p->m_right;
    }
}

最后小结

更加相信递归是种强大的技术，它使我们能够以一种优雅而有效的方式解决许多问题。同时，它也不是解决任务问题的灵丹妙药。由于时间或空间的限制，并不是所有的问题都可以用递归来解决。递归本身可能会带来一些不希望看到的副作用，比如栈溢出。

有时，在解决实际问题时一看，我们并不清楚是否可以应用递归算法来解决问题。然而，由于递归的递推性质与我们所熟悉的数学非常接近，用数学公式来推导某些关系总是有帮助的，也就是说写出递推关系和基本情况是使用递归算法的前置条件。

只要有可能，就应用记忆化。有时，在递归过程中，可能会出现重复计算的情况，例如斐波纳契数（Fibonacci）。在这种情况下，你可以尝试应用 记忆化技术，它将中间结果存储在缓存中供以后重用，它可以在空间复杂性上稍加折中，从而极大地提高时间复杂性，因为它可以避免代价较高的重复计算。

当堆栈溢出时，尾递归可能会有所帮助。

使用递归实现算法通常有几种方法。尾递归 是我们可以实现的递归的一种特殊形式。与记忆化技术不同的是，尾递归通过消除递归带来的堆栈开销，优化了算法的空间复杂度。更重要的是，有了尾递归，就可以避免经常伴随一般递归而来的堆栈溢出问题，而尾递归的另一个优点是，与非尾递归相比，尾部递归更容易阅读和理解。这是由于尾递归不存在调用后依赖（即递归调用是函数中的最后一个动作），这一点不同于非尾递归，因此，只要有可能，就应该尽量运用尾递归。