3

这是一个获取数字的数字总和的函数：

int sumOfDigits(int n)
{
    int sum=0; //line 1
    if(n==0)
        return sum;
    else
    {
        sum=(n%10)+sumOfDigits(n/10); //line 2
        // return sum;  //line 3
    }
}

在编写此代码时，我意识到局部变量的范围对于函数的每个单独递归都是局部的。那么我是否正确地说 if每次递归都会创建n=111115 个sum变量并将其推送到堆栈上？如果这是正确的，那么当我可以使用循环在正常功能中执行递归时，使用递归有什么好处，从而只覆盖一个内存位置？如果我使用指针，递归可能会像普通函数一样占用类似的内存。

现在我的第二个问题，即使这个函数每次都给我正确的结果，我看不出递归（除了返回 0 的最后一个）如何在不取消注释第 3 行的情况下返回值。（使用 geany 和 gcc）

我是编程新手，如有错误请见谅

4

3 回答 3

4

那么我是否正确地说，如果 n=11111，每次递归都会创建 5 个 sum 变量并将其推送到堆栈上？

从概念上讲，但编译器可能会将某些形式的递归转换为跳转/循环。例如，进行尾调用优化的编译器可能会转向

void rec(int i)
{
    if (i > 0) {
        printf("Hello, level %d!\n", i);
        rec(i - 1);
    }
}

相当于

void loop(int i)
{
    for (; i > 0; i--)
        printf("Hello, level %d!\n", i);
}

因为递归调用处于尾部位置：当进行调用时，当前的调用rec除了对调用者 a 之外没有更多工作要做return，所以它不妨将其堆栈帧重用于下一次递归调用。

如果这是正确的，那么当我可以使用循环在正常功能中执行递归时，使用递归有什么好处，从而只覆盖一个内存位置？如果我使用指针，递归可能会像普通函数一样占用类似的内存。

对于这个问题，递归是非常不合适的，至少在 C 中是这样，因为循环更具可读性。然而，存在递归更容易理解的问题。树结构的算法就是最好的例子。

（虽然每个递归都可以通过带有显式堆栈的循环来模拟，然后可以更容易地捕获和处理堆栈溢出。）

我不明白关于指针的评论。

如果没有取消注释第 3 行，我看不到递归（除了最后一个返回 0 的递归）如何返回值。

偶然地。该程序表现出未定义的行为，因此它可以做任何事情，甚至返回正确的答案。

于 2013-06-04T10:20:46.917 回答
2

那么我是否正确地说，如果 n=11111，每次递归都会创建 5 个 sum 变量并将其推送到堆栈上？

递归有 5 层深，因此传统上最终将创建 5 个堆栈帧（但请阅读下文！），每个堆栈帧都有空间来保存一个sum变量。所以这在精神上大多是正确的。

如果这是正确的，那么当我可以使用循环在正常功能中执行递归时，使用递归有什么好处，从而只覆盖一个内存位置？

有几个原因，其中包括：

  • 递归地表达算法可能更自然；如果性能可以接受，可维护性很重要
  • 简单的递归解决方案通常不保持状态，这意味着它们可以简单地并行化，这是多核时代的主要优势
  • 编译器优化经常否定递归的缺点

如果没有取消注释第 3 行，我看不到递归（除了最后一个返回 0 的递归）如何返回值。

注释掉第 3 行是未定义的行为。你为什么要这样做？

于 2013-06-04T10:18:29.517 回答
1

是的，参数和局部变量对于每个调用都是本地的，这通常通过创建程序堆栈上设置的每个调用变量的副本来实现。是的，与使用循环的实现相比，这会消耗更多的内存，但前提是问题可以通过循环和恒定的内存使用来解决。考虑遍历一棵树-您将不得不将树元素存储在某个地方-无论是在堆栈上还是在其他一些结构中。递归的优点是更容易实现（但并不总是更容易调试）。

如果您return sum;在第二个分支中评论行为未定义 - 任何事情都可能发生，包括预期的行为。那不是你应该做的。

于 2013-06-04T10:20:55.493 回答