如何系统地跟踪递归?
好吧,我有许多’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,并且从函数返回。
使用相同的方法,您可以弄清楚上面的函数是做什么的。