C/C++函数递归

Question

我一直在尝试理解下面的代码片段，但对输出背后的逻辑还不太明白。

int Func(int x, int y){
    if (x < y)
        return 0;
    else
        return Func(x - y, y) + 1;
}

int main()
{
    int x = 50, y=10;
    printf("%d  \n",Func(x,y));
    return 0;
}

以上程序的输出显然是5。有人能告诉我递归方法中的"+1"（在return Func(x - y, y) + 1;中）实际上意味着什么，它如何执行流程？

如果我只执行 return Func(x-y,y); 那么输出是0，这是可以理解的。但为什么第一个例子的输出是5？

- Shivaraj Bhat

---

+1 表示在返回 Func 的结果之前将其加一。 - Mark B

如果你不知道该值是如何得出的，那么怎么说这显然是5呢？ - hlscalon

在发布这个问题之前，我已经在Visual Studio中执行过了。我对它的输出感到惊讶，所以才提出了这个问题。 - Shivaraj Bhat

Answer 1

递归将按以下方式进行：

Func(x = 50, y = 10) x >= y 
  Func(x = 40, y = 10) x >= y
    Func(x = 30, y = 10) x >= y
      Func(x = 20, y = 10) x >= y
        Func(x = 10, y = 10) x >= y
          Func(x = 0, y = 10) x < y
          return 0
        return Func(x = 0, y = 10) + 1 = 1
      return Func(x = 10, y = 10) + 1 = 2
    return Func(x = 20, y = 10) + 1 = 3
  return Func(x = 30, y = 10) + 1 = 4
return Func(x = 40, y = 10) + 1 = 5

在递归调用中，+1表示对Func(x - y, y)计算结果加1。

- md5

---

很好的解释 (: +1 - A. Abramov

非常感谢您整洁的回答...它清晰地展现了递归方法的执行过程。 - Shivaraj Bhat

Answer 2

这个方法展示了一个很好的减法概念。无论如何，这里的想法是每次从第一个参数中减去第二个参数，并将1添加到总和中。这样，你就可以检查第一个参数在另一个参数中适合了多少次，或者换句话说，进行了多少次减法。 (:

解释一下具体的+1部分：

最后，当第一个参数低于零时，函数返回零。这样，你就知道什么时候停止了。

每次进行减法运算时，都会将除法总和加1，这是每次迭代的返回值。

- A. Abramov

Answer 3

这是它的作用。 我使用“.”来强制缩进，以便更容易看出我们在递归调用中的位置。

您调用Func（50,10）。

这将调用Func（40,10）。

..这将调用Func（30,10）。

...这将调用Func（20,10）。

....这将调用Func（10,10）。

.....这将调用Func（0,10）。 由于0 <10，因此返回0。

..... Func（0,10）返回0。 将其加1并返回。

.... Func（10,10）返回1。 将其加1并返回。

... Func（20,10）返回2。 将其加1并返回。

.. Func（30,10）返回3。 将其加1并返回。

.Func（40,10）返回4。 将其加1并返回。

因此，Func（50,10）返回5。

因此，实质上，结果5表示它进行了5次递归调用。

- Topological Sort

Answer 4

在基本情况下，Func()返回0。

如果它递归一次，它将返回0 + 1 = 1（基本情况加1）。

如果它递归两次，它将返回(0 + 1) + 1 = 2（基本情况加上1的情况再加1）。

以此类推。因此，返回值表示函数调用自身的次数，这样就可以计算出除法忽略余数的结果。

- Matthew Read

Answer 5

仅分析代码如何执行。首先，您需要进入基本情况（只是调用函数）。现在，您已经调用函数五次，每次都使用不同的参数。当x < y时，您返回并且返回的结果为0。请记住，在这五次中，您什么也没有做，除了更改参数。现在，每次返回时，您都将+1添加到该结果中，因此第一次返回时，您添加+1并获得0 + 1 = 1，然后第二次返回时，您将+1添加到该结果中，并获得1 + 1 = 2，接下来2 + 1 = 3，依此类推。

- Sly_TheKing