递归函数中的返回值

Question

递归函数中的返回值

crecursionreturn-valuefunction-definition

4

我将尝试解释如何在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 i 是什么意思？这段代码是否有意义？

- nounoursnoir

3

在recur函数中，递归调用返回的值会发生什么？你只是将它们丢弃了。另外，我建议您使用调试器逐步执行代码，进入递归调用，并查看会发生什么。 - Some programmer dude

3

编写一个没有实际用途的函数，你将从中学到毫无用处的东西。 - n. m.

嗯，我不知道我缺少什么，但我确实知道我得到了什么：一个我不理解的行为的解释。这段代码实际上是一个简单的测试，以查看递归如何工作，基于输入。 - nounoursnoir

如果你尝试编写一个返回有用值的函数，比如说参数的阶乘，你可能能更快地学会它，而不必四处问询。但无论哪种方法适合你。 - n. m.

我猜不同的人有着不同的学习倾向。对我而言，最容易学习的是概念。而对你或其他一些人来说，最容易学习的可能是那些可以通过具体例子来理解的东西。 - nounoursnoir

显示剩余3条评论

4个回答

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) 返回 2 * pow(2, 2)
第二步： pow(2, 2) 返回 2 * 2* pow(1, 2)
第三步： n == 1 因此pow(1, 2) 返回 x = 2 * 2 * 2 = 8

递归函数在过程的第(i+1)步返回对自身的调用。为了避免无限循环，必须设置一个中断条件，该条件导致返回到与自我调用不同的内容。

- Badda

第二次迭代不应该包含returns pow(1,16)吗？ - Just_chill

1

@PranshuTaneja 你是对的，有趣的是在5年后你是第一个注意到这个错误的人!! 我已经编辑了我的回答。 - Badda

0

你得到了至少一个有用的答案，解释了你的代码行为。

我想通过另一种方式提供帮助。两者结合起来为您提供不同的视角。
为此，我提供了一个增强版本的代码，其中包含仪器，可以更详细地告诉您发生了什么。
这样，您就可以使用代码并观察，这将为您提供真正有用的答案。

注意：

for(c行仅用于暗示缩进；
我选择不使用函数，因为它使有趣的函数调用更突出
我添加了一个参数“嵌套”，它是为了
- 产生部分（希望有用的）输出
- 显示通常递归嵌套会有些影响
我引入了一个局部变量“j”，
以展示在大多数情况下返回值的情况

代码：

#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"。
（特别是不要将 "[]" 与数组混淆，它们不存在。）

- Yunnosch

-1

return 0是从主函数返回的，而不是从您的递归代码返回的。

- Tomaz Canabrava

抱歉，我想说的是 return i 而不是 return 0... 我已经修改了我的代码。 - nounoursnoir

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vlad from Moscow · Accepted Answer

函数的递归调用不会影响返回值。只有在递归函数的第一次实例中遇到的第一个return语句才会将一个值返回给父函数。任何其他遇到的return语句都只会停止程序当前所在的函数实例。

因此，由于函数是以参数0在主函数中调用的

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

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

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

在这种情况下，在向main返回值之前，会调用recur函数。它将创建另一个recur实例，该实例将执行一些操作，但在此recur实例结束后，主要的recur实例将继续，并且在这种情况下，将向main函数返回10。

如果想知道递归函数将返回给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;
}