return 语句中的递归

Question

谁能给我解释一下 return 语句中两个递归函数的执行情况，就像这样

struct node
{
    int data;
    struct node* left;
    struct node* right;
};


struct node* newNode(int data)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

int size(struct node* node) 
{
    if (node==NULL) 
        return 0;
    else    


  return(size(node->left) + 1 + size(node->right));


}


int main()
{

    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);   
    printf("Size of the tree is %d", size(root));  
    getchar();
    return 0;
}

在这种情况下，return 语句中的 size() 函数是如何执行的，是从左到右还是从右到左！我想知道这两个函数的执行流程。

Answer 1

递归由两个概念驱动，传播条件和终止条件。

条件 (node == NULL) 是递归的终止条件， size(node->left) + 1 + size(node->right) 是传播左树和右树的传播条件来自根节点和后续节点的树，并将节点本身的大小加 1。

为了向您全面解释，我们需要一棵示例树


                 3
          4               5
      1        2      9       8

样本树的递归是这样的

size(3)
 = size(4) + size(5)       + 1

现在让我们看看size(4) = size(1) + size (2) + 1 size(1) = size(NULL) + 1 = 0 + 1 = 1（因为 1 没有左边，如果节点为 NULL，则函数 returns 0 - 终止条件）尺寸(2) = 尺寸(NULL) + 1 = 0 + 1 = 1 因此 size(4) 是 3

以类似的方式，size(5) 也将是 3，因此 size(1) = 3+3+1 = 树中的 7 个节点

因此执行是

size (3) 
size (4) + size (5) + 1
size (1) + size (2) + 1 + size(9) +size (8) + 1
size (NULL) + 1 +size (NULL) + 1  + 1 +size (NULL) + 1  +size (NULL) + 1  +1

最终return被

return 0 + 1+ 0+1+1+0+1+0+1+1

return 7

Answer 2

这是序列

size(root)
=size(root->left) + 1 + size(root->right)
=(size(root->left->left) + 1+ size(root->left->right)) + 1 + size(root->right)
=((size(root->left->left->left) + 1 + size(root->left->left->right)) + 1+ size(root->left->right)) + 1 + size(root->right)
=((0 + 1 + size(root->left->left->right)) + 1+ size(root->left->right)) + 1 + size(root->right)
=((0 + 1 + 0) + 1+ size(root->left->right)) + 1 + size(root->right)
=(1 + 1+ size(root->left->right)) + 1 + size(root->right)
=(1 + 1+ (size(root->left->right->left) +1+ size(root->left->right->right)) + 1 + size(root->right)
=(1 + 1+ (0 +1+ size(root->left->right->right)) + 1 + size(root->right)
=(1 + 1+ (0 +1+ 0)) + 1 + size(root->right)
=(1 + 1+ 1) + 1 + size(root->right)
=(3) + 1 + (size(root->right->left)+ 1 +size(root->right->right))
=(3) + 1 + (size(root->right->left->left)+ 1+ size(root->right->left->right))+ 1 +size(root->right->right))
=(3) + 1 + (0+ 1+ size(root->right->left->right))+ 1 +size(root->right->right))
=(3) + 1 + (0+ 1+ 0)+ 1 +size(root->right->right))
=(3) + 1 + (1)+ 1 +(size(root->right->right->left)+1+ size(root->right->right->right))
=(3) + 1 + (1)+ 1 +(0+1+ size(root->right->right->right))
=(3) + 1 + (1)+ 1 +(0+1+ 0)
=(3) + 1 + (1)+ 1 +(1)
=(3) + 1 + (3)
=7

代码序列如下：

//step 1
size(root)
{
    //node===root
    if (root==NULL)//no
        return 0;
    else
        return(size(root->left) + 1 + size(root->right));
        //it will call size(root->left)
       //after size(root->left) it will plus 1 then will call size(root->right)
}
//step 2
size(root->left)
{

    if (root->left==NULL)//no
        return 0;
    else
        return(size(root->left->left) + 1 + size(root->left->right));
}
//step 3
size(root->left->left)
{

    if (root->left->left==NULL)//no
        return 0;
    else
        return(size(root->left->left->left) + 1 + size(root->left->left->right));
}
//step 4
size(root->left->left-->left)
{

    if (root->left->left==NULL)//yes
        return 0;
    //it returns to step 3

}
//step 5 from step 3
size(root->left->left)
{

    if (root->left->left==NULL)//no
        return 0;
    else
        return(0 + 1 + size(root->left->left->right));
       //size(root->left->left->left==0
       //now it calls size(root->left->left->right)
}
//step 6 from step 5

size(root->left->left->right)
{

    if (root->left->left->right)//yes
        return 0;
    //it retuns to step 5
}
//step 7 from step 3
size(root->left->left)
{

    if (root->left->left==NULL)//no
        return 0;
    else
        return(0 + 1 + 0);//==1
       //size(root->left->left->right)==0
       //now it returns to 2
}

希望您了解其余部分。

return 语句中的递归

Recursion in return statement

c

tree

recursion

function

data-structures