Returns 在递归函数中

Question

我想了解如何在 C 中使用递归，但我无法理解 return 在其中的工作原理。

请考虑以下代码：

int     recur(int i)
{
    printf("recur: i = %d\n", i);
    if (i < 3)
    {
        recur(i + 1);
        return 10;
    }
    else if (i < 5)
        recur(i + 1);
    return i;
}

int     main(void)
{
    int     i = 0;
    i = recur(i);
    printf("i = %d\n", i);
    return 0;
}

输出为：

recur: i = 0
recur: i = 1
recur: i = 2
recur: i = 3
recur: i = 4
recur: i = 5
i = 10

最后的 return、return i 是做什么用的？这段代码有意义吗？

Answer 1

return 0 是来自主函数的 return，而不是来自您的递归代码。

Answer 2

函数的递归调用不会影响returned值。只有在递归函数的第一个实例中遇到的第一个 return 才会 return 为父函数赋值。遇到任何其他 return 只会停止程序当前所在的函数实例。

因此在 main 中使用参数 0 调用函数

int     i = 0;
i = recur(i);

遇到的第一个 return 位于 if 语句内：

if (i < 3)
{
    recur(i + 1);
    return 10;
}

在这种情况下，recur 函数在 return 将值设为 main 之前被调用。它将创建另一个 recur 实例来做一些事情，但是在这个 recur 实例结束后， recur 的主实例将继续，在这种情况下，将 return 10 到函数 main.

要了解您的递归函数将 return 传递给 main 函数，您可以简单地注释所有对函数新实例的调用：

int     recur(int i)
{
    if (i < 3)
    {
        //recur(i + 1);
        return 10;
    }
    else if (i < 5)
    {
        //recur(i + 1);
    }
    return i;
}

在这种情况下，程序将读取以下内容：

int     recur(int i)
{
    if (i < 3)
        return 10;
    return i;
}

Answer 3

我认为这是最容易理解的递归函数之一。

int pow(int n, int x)
{
    if (n != 1)
        return x * pow(n - 1, x)
    else 
        return x;
}

学习一下pow(3, 2) : 2^3 = 2 * 2 * 2 = 8

第一次迭代：pow(3, 2) returns 2 * pow(2, 2)
第二次迭代：pow(2, 2) returns 2 * 2* pow(1, 2)
第三次迭代：n == 1 所以 pow(1, 2) returns x = 2 * 2 * 2 = 8

递归函数 return 是在过程的 i + 1 步调用自身。为了避免无限循环，你必须确保你有一个中断条件，这导致 return 与自我调用不同。

Answer 4

您至少得到了一个有助于解释代码行为的答案。

我想在这里通过不同的、额外的途径提供帮助。两者共同为您提供不同的观点。
为此，我提供了一个通过检测增强的代码版本，它更详细地告诉您发生了什么。
这使您可以玩代码并观察，这将为您提供真正有用的答案。

注：

for(c 行仅用于提示性缩进；
我选择不为此使用函数，感觉它使有趣的函数调用更加突出
我加了一个参数"nesting"，是为了
- 制作一部分（希望有用）输出
- 表明通常递归嵌套有一定的影响
我引入了一个局部变量"j",
显示在大多数情况下 reutrn 值会发生什么

代码：

#include <stdio.h>

int     recur(int i, int nesting)
{   int c;
    for(c=0;c<nesting;c++) { printf(" ");}
    printf("recur[%d](%i)", nesting, i);
    if (i < 3)
    {   printf("i <3, calling recur[%d](%d)\n", nesting+1, i+1);
        recur(i + 1, nesting+1);
        for(c=0;c<nesting;c++) { printf(" ");}
        printf("returning 10 from recur[%d], with i==%d\n", nesting, i);
        return 10;
    }
    else if (i < 5)
    {
        int j=0;
        printf("i <5, calling recur[%d](%d)\n", nesting+1, i +1);
        j=recur(i + 1, nesting+1);
        for(c=0;c<nesting;c++) { printf(" ");}
        printf("ignored return value from recur[%d](%d) is %d", nesting+1, i+1, j);
    }

    printf("\n");
    for(c=0;c<nesting;c++) { printf(" ");}
    printf("returning i from recur[%d], with i==%d\n", nesting, i);
    return i;
}

int     main(void)
{
    int     i = 0;
    i = recur(i, 0);
    printf("the last return value did not get ignored: i = %d\n", i);
    return 0;
}

输出：

recur[0](0)i <3, calling recur[1](1)
  recur[1](1)i <3, calling recur[2](2)
    recur[2](2)i <3, calling recur[3](3)
      recur[3](3)i <5, calling recur[4](4)
        recur[4](4)i <5, calling recur[5](5)
          recur[5](5)
          returning i from recur[5], with i==5
        ignored return value from recur[5](5) is 5
        returning i from recur[4], with i==4
      ignored return value from recur[4](4) is 4
      returning i from recur[3], with i==3
    returning 10 from recur[2], with i==2
  returning 10 from recur[1], with i==1
returning 10 from recur[0], with i==0
the last return value did not get ignored: i = 10

注：
recur[n](m) 当然不是 C 语法。
它仅指示在嵌套级别 "n" 上使用参数 "m".
调用函数 "recur" （尤其不要将“[]”与数组混淆，它们不存在。）

Returns 在递归函数中

Returns in a recursive function

c

recursion

return-value

function-definition