logo标签列表

如何系统地跟踪递归？

crecursion
3

嗯，我有很多关于寻找给定函数输出的'C语言'测试，此外，我需要准确地解释它的目的。其中一些是递归函数。当我遇到递归时，我总是苦苦挣扎着如何按照图表跟随它，即使我成功了，有时我也可能不理解递归函数的目的。

这里有两个代码片段：

Main函数

#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。

我的问题是：我如何在纸上按照图表的方式跟踪它并理解它的目的。或者，你们会如何处理这种问题？任何帮助都将不胜感激！

2
在非学术环境中，我会建议编写该代码的人使用更具描述性的名称。 - Colonel Thirty Two
回答你问题的另一部分，对于确定某段代码的功能，我通常不会完全追踪执行过程，而是会用力地盯着它直到问题变得明显（费曼算法）。或者我会尝试使用简单的输入进行一些子例子，并插入一些断点来检查情况，以此逐步从细节中建立起含义。这相当于手动反汇编代码，这是一种合法的技能，没有单一的“正确”方法，甚至可以被看作一种艺术。 - Cameron
ColonelThirtyTwo已经掌握了这个技能。递归代码的编写和验证并不难 - 只需分别查看基本情况和递归情况，然后决定哪种情况适用即可。在现有的递归代码中，也很容易看到基本情况和递归情况等。只凭实现来推断其目的并不容易，除非是一些微不足道的情况。显然，这是一个有意将意图隐藏起来的解码挑战。不幸的是，这有时是必要的技能。 - user180247
4个回答
3
我们在学校也需要这样做，在考试期间写起来很费时间，但确实有助于理解。
基本上，你会得到一个执行“堆栈”，就像编译器和运行时在幕后使用的那样来实际执行代码：从主函数开始，一些变量被设置。这是堆栈的顶部。然后，主函数调用f2，将该调用推送到堆栈上。这个新的“堆栈帧”具有不同的局部变量。在该帧中写下它们的值。然后，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)
...
我理解你的意思。假设我成功了，我能从我写的方案中看到递归函数的目的吗？ - Ilan Aizelman WS
取决于您所说的“目的”;-) 您将能够准确地看到它是如何得出结果的 - 这不会是一个谜 - 但是这是否有助于您理解代码的工作原理则是另一个问题。您可以分析人工神经网络并查看哪些“神经元”触发了它们的阈值，但这并不能真正帮助理解为什么特定的神经网络仅在输入猫的图片时产生积极的结果。 - Cameron
我明白了。感谢你的时间！我醒来后会回答这个问题。晚安！ - Ilan Aizelman WS
2
我不会再添加之前的堆栈示例，因为它们可能来自我的讲座材料。
我想要讲解@Edwin给你的三个部分：它们是你的关键工具。 我通常会颠倒前两个。 应用于你的特定问题：
终止条件：只要n为正且x不为0，我们就继续执行。 当我们失败其中任何一个检查时，我们返回x == 0（将返回值解释为false / true）。
返回结果：请注意，这个布尔值也是唯一的返回结果。
递归：我们尝试使用较小的问题调用函数：
从数组a中删除第一个元素。
从x中减去该值
减少n
{现在，我们已经学到了什么：n是计数器；x是运行总和，我们已经得到了最终结果；a是组件列表。}
现在，如果这成功返回（返回true），则我们将该true传回调用堆栈（这是三元表达式中的1）。 如果失败，则尝试上面的项目符号步骤，但不减少x。 然后将此结果回传，无论其价值如何。
所以大致情况如下：
如果在n降至0之前x变为0，我们获胜。
如果n为0时x！= 0，则失败。
在那之前，我们的“尝试下一个”步骤是获取下一个可用数字。 从x中减去它，然后使用（a）列表的剩余部分；（b）少一次尝试（这是n），以及（c）正确减少的运行总和再次调用自己。 如果那不起作用，请跳过此数字并尝试下一个数字。
顺便说一下，最后一个调用的中间术语应该是n，而不是n-1吗？ 当我们跳过a [0]时，我们没有使用一次猜测。
话虽如此，我真的质疑这门课程试图教授什么。 除非这个问题是一个孤立的例子，否则我认为它并不打算将您变成专业程序员。 代码未经注释，标识符来自穿孔卡片时代，返回值是“魔法数字”。
我们需要更多像您这样的人存在于地球上。 - Ilan Aizelman WS
顺便提一下，当我读到“x是一个运行总和”时，我完全理解了该函数的目的。 - Ilan Aizelman WS
1
很高兴能帮上忙。是的，“x 是一个累加和”可能是至关重要的洞见。当它被倒序管理时，需要练习才能识别出它。从这个线索中就理解了其余部分是个好兆头——你会做得很好。 - Prune
2
理解递归函数最好的方法是掌握演绎推理，使用分治策略解决简单问题。虽然这种方法并不适用于所有递归问题，但适用于80%以上的递归情况。
基本上你需要发现递归方案的三个要素： 1. 一个演绎规则（或一组规则），将问题缩小为更小的问题。 2. 一组终止规则，设计得可以确保到达它们。 3. 某处用于保存中间结果的位置（通常是调用堆栈，有时是堆上的堆栈）。
为了举例说明，我们将使用我能想到的最愚蠢的例子，尝试计算字符串长度，通常你会使用while循环（假设你不使用系统库等）。
 (pseudo code)

 int length = 0;
 while (current_char != newline) {
    length = length + 1;
    current_char = next_char;
 }

递归策略就像

(pseudo logic)

The length of a string is one more than the length of a string with one less character
The length of the "" string is zero

(pseudo java code)
int recursive_length(String s) {
   if (s.equals("")) {
     return 0;
   }
   return 1 + recursive_length(s.substring(1))
}

对于 recursive_length 的调用，您的调用栈会像这样增长
recursive_length("hello");

这将被评估为

{1 + recursive_length("ello")}

该表达式的计算结果为

{1 + {1 + recursive_length("llo")} }

该表达式的结果为

{1 + {1 + {1 + recursive_length("lo")} } }

该表达式的值为

{1 + {1 + {1 + {1 + recursive_length("o")} } } }

评估结果为
{1 + {1 + {1 + {1 + {1 + recursive_length("")} } } } }

由于显式终止规则，现在它的计算结果为 

{1 + {1 + {1 + {1 + {1 + {0}}}}}}

当我们从最内层的调用返回时，它被求值为

{1 + {1 + {1 + {1 + {1 + 0}}}}}

然后加法操作发生（最终）。
    {1 + {1 + {1 + {1 + {1}}}}}

然后我们从那个调用中返回

{1 + {1 + {1 + {1 + {1 + 1}}}}

还有一个新增

{1 + {1 + {1 + {1 + {2}}}}}

以此类推

{1 + {1 + {1 + {1 + 2}}}}
{1 + {1 + {1 + {3}}}}
{1 + {1 + {1 + 3}}}
{1 + {1 + {4}}}
{1 + {1 + 4}}
{1 + {5}}
{1 + 5}
{6}
6

那么，所有这些中间的1 + ...是如何保留的呢？它们在调用栈中，随着我们评估下一个递归调用而退出。当内部调用返回时，代码会向上移动调用栈，累积答案。
由于递归非常依赖于堆栈，因此它自然适合某些类型的数据结构。唯一的问题是，如果算法出错，您永远无法达到终止状态，并且堆栈会不断增长。
为了解决这个问题，执行环境监视调用堆栈的进展，当感觉到堆栈太深时，就会使用StackOverflow错误中断程序。
在这个例子中，我在函数内部调用函数的事实是我正在使用递归。硬编码测试的早期退出条件是明显的终止规则。返回结果显然是归纳推理，将问题分解成更小的问题。
这意味着验证递归函数通常是一个逻辑问题，而不是一个编程问题。但有时候即使是最好的逻辑论证也会被编程错误所破坏 :)
跟踪执行过程中最重要的部分是记录各种堆栈中的状态。在本例中，我使用括号，但只要您有一种一致的方法来跟踪它们，使用什么符号都无所谓。
1

使用堆栈是跟踪递归函数的最佳方法。以阶乘函数为例。

long fact(int n)
{
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}

这是 fact(4) 的样子。

enter image description here

在堆栈的底部是基本情况：1的阶乘是1。现在我们知道1的阶乘是1，我们知道2的阶乘是2 * 1，即2。但是既然我们知道2的阶乘是多少，我们可以解决3的阶乘，即3 * 2，即6。现在我们知道3的阶乘是多少，因此我们可以解决4的阶乘，或者4 * 6，即24。所有调用都已从堆栈中弹出。因此，我们知道4的阶乘是24，并且从函数返回。
使用相同的方法，您可以弄清楚上面的函数是做什么的。
1
为什么会有踩？我说过我正在编辑的过程中。 - lost_in_the_source
总的来说，这很棒（比我在答案中提出的方法快得多），但当递归函数调用自身超过一次时（如 OP 的示例），以这种方式跟踪变得更加棘手。顺便说一句，我没有投反对票，不确定为什么会发生这种情况 :/ - Cameron
@stackptr 我知道这一点，但是在我的函数中有两个递归函数。当我醒来并尝试将其再次写在纸上时，我会提出问题并看看是否可以从Cameron所写的原理图中理解其目的。感谢您的时间！ - Ilan Aizelman WS
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接