c - C中的递归，了解递归示例

Question

我无法理解这个例子。我无法弄清楚在某一点之后实际发生了什么。

这是代码，结果应该是4。

我可以看到它多次调用自己，但它实际上是如何得出 4 的结果的，我完全不知道。任何帮助将不胜感激。

#include <stdio.h>

int recursion(int i) 
{ 
  return (i>1 ? i - recursion(i/2) : 3);
} 

int main() 
{ 
  int number = 9; 
  printf("The result is %d\n", recursion(number)); 
  return 0;
}

编辑： 非常感谢，这清除了它！

Answer 1

这里来自代码， recursion(1) = 3以及i/2何时i>1，9/2 = 4（因为 int 作为参数）

这个递归函数的基本条件是当i = 1

Answer 2

我认为理解这一点的最好方法就是在调试器中单步执行。

Answer 3

你可以通过代入和简化来推理这个问题。

你开始调用递归（9），让我们用 9 代替 i 并减少

recursion(9)
->  9 > 1 ? 9 - recursion(9/2) : 3
->  true ? 9 - recursion(4) : 3
->  9  - recursion(4)

现在你做recursion(4)了，为了简化这个你可以重复这个过程......

recursion(4)
->  4 > 1 ? 4 - recursion(4/2) : 3
->  true  ? 4 - recursion(2) : 3
-> 4 - recursion(2)

recursion(2)
-> 2 > 1 ? 2 - recursion(2/2) : 3
-> true ? 2 - recursion(1) : 3
-> 2 - recursion(1)

recursion(1)
-> 1 > 1 ? ... : 3
-> false ? ... : 3
-> 3

在这里，您得到了最终结果，因此将其替换回recursion(1)

2 - 3 -> -1

和recursion(2)

4 - -1 -> 5

和recursion(4)

9 - 5 -> 4

Answer 4

递归是重复自身多次直到条件为真的过程。

如果 i>1 为 false，则函数递归返回值 3，如果为 true，则递归调用。

当 i=9 时，它第一次检查 9>1 为真。因此，函数返回 9 - recursion(9/2=4)，因为 i 是 int。

然后它调用 recursion(4) 4>1 因此，返回 4 - recursion(4/2=2)

再次 2>1，返回 2 - 递归（1）

再次 1>1 为假，它返回 3 应替换为上述值，即 2-3 = -1。

然后 4 - (-1) = 5

9 - 5 = 4。

Answer 5

您应该查看调用是如何链接的。调试输出有助于：

int recursion(int i) 
{ 
   int result;
   printf( "called with i=%d\n", i );
   result = (i>1 ? i - recursion(i/2) : 3);
   printf( "call with i=%d will return %d\n", i, result );
   return result;
} 

基本思想是，当递归调用完成时，原始调用将暂停，直到递归调用结束。

Answer 6

递归函数可以通过这种方式以不太紧凑的方式编写：

int recursion(int i) 
{ 
    if(i>1)
    {
        int j;
        j = i - recursion(i/2); // note here that the function recall itself
                                // note also that as i is integer the function
                                // will be invoked with i/2 rounded to the lower int value
        return j;
    }
    else
    {
        return 3;
    }
}

希望这可以帮助...