c++ - 需要简单的 c++ 递归解释

Question

我目前正试图围绕递归进行思考，所以我选择了一本 c++ 教科书并开始阅读。递归一章的前几页很容易理解，但后来我遇到了一个对我来说没有意义的项目。

 int height(node *p)
 {
    if(p==NULL)
       return 0;
    else{
   return 1 + max(height(p->llink),height(p->rlink));

  }

如果 max 给了我两个值中的最大值， max 如何从它返回的高度获取它的参数。如果有人可以提供帮助，我将不胜感激......

Answer 1

要理解递归，您必须递归地思考：

• 你可以理解一棵空树的高度为0
• 您可以理解，通用非空树的高度为 1 + 最长子树的高度（可以是从左侧或从右侧开始的子树）

从这里开始，您可以轻松理解代码。如果你画树，你会看到会发生什么。如果你有例如

     A
    / \
   B   C
  / \  
 D   E

• height(A)将返回1 + max(height(B), height(C))
• height(B)将返回1 + max(height(D), height(E))
• height(C)将返回1 + max(height(NULL), height(NULL)) = 1
• height(D)将返回1 + max(height(NULL), height(NULL)) = 1
• height(E)将返回1 + max(height(NULL), height(NULL)) = 1

所以

height(A) = 1 + max(height(B), height(C)) =
= 1 + max(1 + max(height(D),height(E)), 1) =
= 1 + max(1 + 1, 1) = 1 + max(2, 1) = 3

（我省略了调用，height(NULL)因为它们是微不足道的 0，否则它会太冗长。）

Answer 2

函数的参数在函数调用之前进行评估。

因此，您的等效示例可能如下所示（这可能更有意义？）：

int height(node *p)
 {
    if(p==NULL)
       return 0;
    else{
       int heightLeftSubtree = height(p->llink);
       int heightRightSubtree = height(p->rlink);
       return 1 + max(heightLeftSubtree, heightRightSubtree);
    }
 }