如何系统地跟踪递归?

好吧,我有许多’C语言’测试涉及查找给定函数的输出,而且,我需要准确解释它的目的是什么。 其中一些是递归函数。 当我遇到递归时,我一直在努力寻找如何示意地遵循它 ,即使我成功了,有时我也可能不明白递归函数目的是什么。

这是2段代码:

主要

#include  #include  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(); } 

f2function:

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

好吧,该函数的“目的”是检查数组中是否有一组数字,它们的和将给出x的值。 (在该特定示例中,x = 5)。 在这种情况下,它将返回true,因为2,3在数组内,2 + 3 = 5。

我的问题是:我如何在纸面上示意地遵循它并理解其目的。 或者,你们将如何处理这类问题? 任何帮助都非常感谢!!

我不会添加到我之前的堆栈示例; 他们本可以从我自己的讲课材料中拿走。

我想要@Edwin给你的三件作品:那些是你的关键工具。 我通常会逆转前两个。 适用于您的具体问题:

终止:只要n为正 x不为0,我们就会继续。当我们对这些检查中的任何一个失败时,我们返回x == 0(将返回值解释为false / true)。

返回结果:请注意,此布尔值也是唯一的返回结果。

递归:我们尝试使用较小的问题调用函数:

  • 从arraysa中切出第一个元素。
  • x中减去该值
  • 递减n

{注意到目前为止我们学到的东西: n是一个柜台; x是一个运行总和,我们已经得到了最终结果; a是组件列表。}

现在,如果返回成功(返回true),那么我们将该true传递给调用堆栈(这是三元表达式中的1 )。 如果失败,我们再次使用上面的项目符号步骤,除非不减少x 。 然后将该结果传递回该行,无论其值如何。

所以细分是这样的:

  • 如果我们到达x为0的地方,那么在n降到0之前的任何时候,我们都会获胜。
  • 如果我们在n命中0时有x!= 0,我们就会失败。
  • 在那之前,我们“尝试下一步”的步骤是抓住下一个可用的号码。 从x中减去它,然后用(a)列表的其余部分再次调用自己; (b)少尝试(即n ),以及(c)适当减少运行金额。 如果这不起作用,请跳过此数字并尝试下一个。

顺便说一下,最后一次通话的中期应该是n ,而不是n-1 ? 当我们跳过[0]时,我们没有用尽猜测。


那就是说,我真的很怀疑这门课程的教学内容。 除非这个问题是一个孤立的例子,否则我不认为它会让你变成一个专业的程序员。 代码是未注释的,标识符来自穿孔卡片日,返回值是“幻数”。

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

基本上,你最终得到一个执行堆栈 ,就像编译器和运行时使用幕后实际执行代码一样:你从main开始,使用一组变量。 这是堆栈的顶部。 然后主要调用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) ... 

理解递归函数的最佳位置是对演绎推理进行快速研究,使用分而治之的策略来解决一些简单的问题。 这不会涵盖每个递归问题,但它涵盖了人们使用递归的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 + ... s? 好吧,它们在调用堆栈中,当我们评估下一个递归调用时,它正在退出。 当内部调用返回时,代码向上移回调用堆栈,累积答案。

由于递归非常面向堆栈,因此它非常适合某些类型的数据结构。 唯一的问题是,如果你弄乱你的算法,你永远不会达到你的终止状态,你永远会增加你的堆栈。

为了解决这个问题,执行环境正在监视调用堆栈的进度,当它感觉太深时,它会使用StackOverflow错误中断程序。

我这个例子我在函数中调用函数的事实是提示我是递归的。 具有硬编码测试的早期退出条件是明显的终止规则。 返回的结果显然是归纳推理,将问题分解为较小的问题。

这意味着validation递归函数通常是逻辑问题,而不是编程问题。 有时候还有编程错误可以阻止最好的逻辑参数:)

跟踪执行过程中最重要的部分是记录各种堆栈中的状态。 为了在这个例子中这样做,我使用了括号,但只要你有一致的方法来跟踪它们,你使用的符号并不重要。

遵循递归函数的最佳方法是使用堆栈。 让我们以阶乘函数为例

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

这就是fact(4)样子

在此处输入图像描述

在堆栈的底部是基本情况:1阶乘是1.现在我们知道1阶乘是1,我们知道2阶乘是2 * 1,它是2.但是因为我们知道2阶乘是,我们可以解决3阶乘,即3 * 2,即6。现在我们知道3阶乘是什么,所以我们可以求解4阶乘,或4 * 6,即24。所有的调用都从栈中弹出。 因此,我们知道4阶乘是24,并且从函数返回。

使用相同的方法,您可以弄清楚上面的函数是做什么的。