c - 如何系统地遵循递归？

Question

嗯，我有许多“C 语言”测试涉及查找给定函数的输出，此外，我需要准确解释它的目的是什么。其中一些是递归函数。而当我遇到递归时，我总是苦苦寻找如何遵循它的示意图，即使我成功了，有时我也可能不明白递归函数的目的是什么>.

这里有两段代码:

主要

#include <stdio.h>
#include <conio.h>

int f2(int *a, int n, int x);
int main()
{
  int a[6] = {4, 3, 4, 2};  
  printf("%d\n", f2(a, 4, 5)); 
  getch();
}

f2函数:

int f2(int *a, int n, int x)
{
  if(n>0 && x!=0){
    return (f2(a+1,n-1,x-a[0]) ? 1 : f2(a+1,n-1,x));
  }
  return (x ? 0 : 1);
}

这个函数的“目的”是检查数组中是否存在一组数字，它们的总和将给出 x 的值。 (在此特定示例中为 x=5)。在这种情况下，它将返回 true，因为 2,3 在数组中，并且 2+3=5。

我的问题是:我怎样才能在纸面上按照示意图遵循它并理解它的目的。或者，你们将如何处理这种问题？ 任何帮助都非常感谢!

Answer 1

我们在学校也必须这样做，在考试期间花了很长时间才写出来，但它确实有点强制理解。

基本上，您最终会得到一个执行堆栈，就像编译器和运行时在幕后使用来实际执行代码一样:您从 main 开始，带有一组特定的变量。这是堆栈的顶部。然后 main 调用 f2，将该调用压入堆栈。这个新的栈帧有不同的局部变量。在这个框架上写下他们的值(value)观。然后 f2 调用自身，将另一个帧插入堆栈(它是相同的函数，但使用不同的参数对其进行不同的调用)。再次记下这些值。

当函数返回时，将其出栈，并记下返回值。

它可以帮助使用缩进来指示当前的堆栈深度(或者如果你有空间就写出整个堆栈)。一般来说，整个程序调用只涉及几个变量，因此将它们放入一个表中是有意义的(这样更容易跟踪正在发生的事情)。

一个简短的例子:

Stack        |    a    |  n  |  x  | ret
-----------------------------------------
mn               4342     4     5
mn f2            4342     4     5
mn f2 f2          342     3     1
mn f2 f2 f2        42     2    -2
mn f2 f2 f2 f2      2     1    -6
mn f2 f2 f2 f2 f2         0    -8     0
mn f2 f2 f2 f2     (2     1    -6)
mn f2 f2 f2 f2 f2         0    -6     0
mn f2 f2 f2 f2     (2     1    -6)    0
mn f2 f2 f2       (42     2    -2)
...