c - 为什么这种递归会作为返回值呢？

Question

我们使用值n来执行递归。我们将此值保存在变量 x 中。然后变量 x 作为返回值添加到递归中。这到底是如何工作的？

我尝试了不同的方法来检查您是否首先对 x 使用递归，然后使用 x 将其添加到另一个递归。

#include <stdio.h>
#include <stdlib.h>

int up(int n)
{
    int x;

    if(n == 0)
    {
        return 0;
    }
    else if(n == 1)
    {
        return 1;
    }
    else
    {
        x = up(n - 2);
        return x + up(n - 1);
    }
}

int main(void)
{
     int n = 20;
     int res;
     res = up(n);
     printf("Result %d\n", res);
     return 0;
}

结果是 6765。由于这是学校的代码，所以结果应该没问题。我只是不明白为什么。

Answer 1

听起来您在理解递归函数作用域的概念时遇到了问题。通常最容易将递归视为树/堆栈。

堆栈:

举个简单的例子，假设 n=5。Up(5) 被压入堆栈。然后声明该函数作用域内的 x 为 UP(3)。现在UP(3)被压入堆栈，UP(5)正在等待Up(3)返回。堆栈顺序:
上(3)
向上(5)

现在 Up(3) 在此函数内声明 x 为 UP(1) 并耐心等待 Up(1) 返回。由于 x 是在函数内部声明的，因此它们是局部变量，只能在声明它们的函数内部访问。这意味着 Up(3) 内部的 X 与 Up(5) 内部的 X 存储在内存中完全不同的位置。当您研究地址空间以及局部变量的存储方式等时，您肯定会了解更多相关知识。但继续前进!

堆栈:
上(1)
上(3)
上(5)
Up(1) 返回 1，因此我们将其从堆栈中弹出!这意味着Up(3)可以继续运行。堆栈:
上(3)
上(5)
Up(3) 现在 x=1(Up(1) 的返回值，并希望返回 x+Up(2)。为此，我们将 Up(2) 压入堆栈。

堆栈:
向上(2)
上(3)
上(5)


继续这个例子，Up(2)会将Up(0)添加到堆栈中。 Up(0) 将返回 0，因此 Up(2) 范围内的 x 设置为 0。然后 Up(2) 将把 Up(1) 添加到堆栈，这将返回 1。Up(2) 将返回(0+1)。现在我们可以通过将 Up(2) 从堆栈中弹出来返回到 Up(3)。 Up(3) 有 x=1 并且希望返回 (1+1)。将 Up(3) 从堆栈中弹出后，堆栈上只剩下 Up(5)。由于 Up(3) 的返回，X 现在设置为 2。现在我们将 Up(4) 添加到堆栈中，从而按顺序添加 Up(2),Up(0),Up(1),Up(3),Up(2),Up(0),Up(1)注意(在添加新调用之前，许多调用都会被弹出)。

我建议阅读有关全局作用域和函数作用域的内容。理解这些概念对于理解递归的基础知识非常重要。然而，您已经可以看到这种类型的递归非常暴力，根本没有优化。例如，您为创建的每个递归调用多次计算 Up(2)。当处理较大的数字时，这会导致可扩展性问题，因为您要对同一数字多次重复相同的操作。对于较小的 Big O 运行时，可以使用内存数组和更多的逻辑来解决这个问题，但这对于这个问题来说可能有点太详细了。