需要简单的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,否则会过于冗长.)