c - return 语句中的递归

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 8 年前。

Improve this 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

Recursion goes like this for sample tree

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

现在让我们看看size(4) = size(1) + size(2) + 1size(1) = size(NULL) + 1 = 0 + 1 = 1(因为 1 没有剩余，如果节点为 NULL，则函数返回 0 - 终止条件)大小(2) = 大小(NULL) + 1 = 0 + 1 = 1因此大小(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 0 + 1+ 0+1+1+0+1+0+1+1 

返回7