此递归代码的 return 值是什么意思？

Question

我无法理解这种递归代码，我该怎么做才能理解这样的函数。你能帮我解释一下这个函数的作用吗（一个例子会有很大帮助）。

typedef struct node* Nodeptr;
typedef struct node{
    int key;
    Nodeptr left,right;
}Node;

Answer 1

解释函数没有通用的规则。了解它们在没有记录时的作用需要经验。

在递归函数的情况下，我们可以尝试从函数的基本情况建立一些理解并从那里开始工作。基本情况或情况是函数不调用自身的情况：它直接产生答案，无需递归。在这个函数中，有两个基本情况。第一个是：

if (!t)
    return NULL;

这是一个简单的案例：如果函数传递了一个空指针，它 returns 一个空指针并且不会改变 *a.

另一个是：

if (t->left == t->right)
{
    *a = t->key;
    return t;
}

与一样，这是对叶节点的混淆测试：如果left或right指向，则t->left == t->right在适当的二叉树中永远不会为真另一个节点。当且仅当 left 和 right 都是空指针时为真，因此这是一个叶节点（它没有任何子节点）。

因此，对于叶节点，函数 returns 节点 (t) 并将 *a 设置为其键的值。

然后我们有递归的情况：

x = f(t->left, &b);
y = f(t->right, &c);
*a = b>c ? b+t->key : c+t->key;
return b>c ? x : y;

前两行对于二叉树上的递归函数是通用的：我们将函数应用于左子树和右子树。（请注意，如果传递的指针为空，则 b 或 c（以传递的那个为准）不会更改（由于上面的基本情况），因此它保持其初始值零。）

然后 *a = b>c ? b+t->key : c+t->key; 将 t-key 添加到 b 或 c 中的较大者，并将 *a 设置为总和。来自其他子树的值将被忽略。因此，我们正在计算某种最大值。

然后return b>c ? x : y; returns指向我们使用其值的节点的指针。因此，它 returns 表明我们从哪里获得最大值。

现在我们知道这棵树对它下面的一层子树做了什么：它计算当前键的值加上它下面的键的最大值，并将总和放入 *a。它 returns 指向我们从中获取值的叶节点的指针。

据此，我们可以弄清楚它对两级子树的作用：它计算当前键的值加上它进行的两次调用的最大值。所以它是从两条路径中选择最大和。它 returns 与它选择的和相关联的指针，开始时是指向叶节点的指针。所以函数总是returns一个指向正在使用的路径末尾的叶节点的指针。

总的来说，该函数计算从根到叶的任何路径上的最大总和，并将其放入 *a。它 returns 指向路径末端叶子的指针。

注意上面假设 key 是非负数。如果某些 key 值为负，它们可能会被为空子树计算的零值覆盖。

what is the return value of this recursive code means?