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呢？

Answer 1

归根结底，除法是一个很棒的减法。这就是这个方法所展示的概念。无论如何，这里的想法是函数每次从第一个参数中减去第二个参数，并添加到总和 1。这样，您检查第一个参数在另一个参数中有多少次，或者换句话说，减去。 (:

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

最后，函数 return 为零 - 当第一个参数小于零时。这样，您就知道何时停止。

每减一次，除法总和加一，即每次迭代的return值。

Answer 2

递归将按如下方式进行：

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表示："add 1 to the result computed by Func(x - y, y) in a recursive call".

Answer 3

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

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

如果递归两次，则returns (0 + 1) + 1 = 2（基本情况，加1情况，加1）。

等等。因此，return 值表示函数调用自身的次数，这（正如另一个答案所说）计算忽略余数的除法。

Answer 4

这是它的作用。我用。强制缩进，以便更容易地查看我们正在进行的递归调用。

你调用 Func(50, 10)。

.这调用 Func (40, 10).

..这调用 Func (30, 10).

...这会调用 Func (20, 10)。

.....这调用 Func (10, 10).

.....这调用了 Func (0, 10)。由于 0 < 10，因此 returns 0.

.....Func(0,10) returned 0. 加 1 然后 return 那.

.....Func(10,10) returned 1. 加 1 然后 return 那.

...Func(20,10) returned 2. 加 1 然后 return 那。

..Func(30,10) returned 3. 加 1 然后 return 那.

.Func(40,10) returned 4. 加 1 然后 return 那.

Func(50,10) 因此 returned 5.

因此，本质上，结果 5 表示它进行的递归调用次数，即 5。

Answer 5

分析一下代码是怎么回事。首先你回到基本情况（只是调用函数）。现在你调用了函数五次，每次都是不同的参数。当 x < y 时，你返回，结果 return 为 0。请记住，你下降了 5 次，除了更改参数外什么也没做。现在每次 return 返回时，都会将 +1 添加到该结果中，因此第一次返回时添加 +1 并得到 0+1 = 1，然后第二次返回时将 +1 添加到该结果结果是 1+1=2，下一次是 2+1=3，以此类推。

C/C++函数递归

C/C++ function recursion

c

c++

recursion