recursion

（受归并排序与树遍历的启发）

归并排序的代码见归并排序

/*求长子兄弟树的高度的算法*/

int Height(EBNode * t)  // 求 t 的高度
{
    if (t == NULL) return 0;  // 空树的高度为 0
	
	int maxsh = 0;
    EBNode * p = t -> eson;   // p 指向 t 结点的长子
    
    while (p != NULL)
    {
        EBNode * q = p -> brother;  // q 临时保存结点 p 的兄弟结点
        int sh = Height(p);         // 递归求结点 p 的子树的高度
        maxsh = max(maxsh, sh);     // 求结点 t 的所有子树的最大高度
        p = q;
    }
    return maxsh + 1;
}

(1) 明确递归终止条件

” 切记写递归算法必须写终止条件，否则便是无限循环！”

1. 归并排序算法中有一行很容易忽略的语句：

// 这一句必须加上！！因为当递推到只有一个结点的时候，这句话就是终止条件！
   if (!head || !head->next) return head;

乍一看以为只是一句异常处理，其实是终止条件！因为当递推到只有一个结点的时候，就不需要也不能够再一分为二、对左右递归排序了，这就是我们的终止情况。
如果不写这一句，那么会导致无限循环！

1. 在求树的高度的算法中：

EBNode * p = t -> eson;   // p 指向 t 结点的长子
    while (p != NULL)

若当前结点为叶子结点，则p=NULL，直接跳过循环，执行return maxsh+1。

（2）总是被递归绕晕怎么办？

不要试图模拟递归，人脑是模拟不过来的。要给予我们的算法充分的信心，相信它能自己处理好。

1. 首先，只模拟一下第一层递归的过程，浅尝辄止

以文首的Height(p)算法为例，首先模拟一下：

• 对于一个根结点t，直接下到其长子结点p（因为根节点没有兄弟），然后对p调用Height(p)求出以p为根结点的子树的高度 ；
• 然后，置maxsh=Height(p)；
• 接着令p=p->brother，遍历p的所有兄弟结点，并依次对它们使用Height(p)，如果有Height(p)大于当下的maxsh，就更新maxsh=Height(p)；
• 至于这些Height(p)到底是怎么实现的，我们并不关心；
• 如此，我们就得到了以这个t为根节点的子树的高度

1. 然后，我们模拟一下终止条件

• 当p指向了一个叶子结点的时候，p=t->eson，故而p=NULL，所以直接跳过循环；
• 那么，我们现在能够做的，只有将maxsh+1，表示高度因为这个叶子结点的存在又多了一层；
• 那么，这个maxsh+1的操作是否对各层次的递推都有效呢？由于每次递推到新的一个子结点，就说明高度又多了一层，所以在循环外部添加一句return maxsh+1;，就能使得在Height()的每一次递推中，都使maxsh+1，显然是合理的；

1. 此外，要明晰的是，“递”和“推”的代码是两部分：

   “[递]”的代码要放在[while循环里]，因为要逐层递推知道不符合while条件；
   而“[归]”，即在回归的过程中解决问题的代码，是放在[while循环外面]的；
   （因为是在 每次从下一层跳回上一层的时候 执行解决问题的代码）

（3）递归是在“归”的过程中解决问题的

比如Height算法，就是在 从叶子结点逐层回归到根节点的过程中 ，每次都令高度＋1，最后得到总高度的。
![[991dbb82935a3d3f4e94b728730adfe.jpg]]

补充：可以看看这个链接：怎么理解递归