1

I've been writing (unsophisticated) code for a decent while, and I feel like I have a somewhat firm grasp on while and for loops and if/else statements. I should also say that I feel like I understand (at my level, at least) the concept of recursion. That is, I understand how a method keeps calling itself until the parameters of an iteration match a base case in the method, at which point the methods begin to terminate and pass control (along with values) to previous instances and eventually an overall value of the first call is determined. I may not have explained it very well, but I think I understand it, and I can follow/make traces of the structured examples I've seen. But my question is on creating recursive methods in the wild, ie, in unstructured circumstances.

Our professor wants us to write recursively at every opportunity, and has made the (technically inaccurate?) statement that all loops can be replaced with recursion. But, since many times recursive operations are contained within while or for loops, this means, to state the obvious, not every loop can be replaced with recursion. So...

For unstructured/non-classroom situations,

1) how can I recognize that a loop situation can/cannot be turned into a recursion, and

2) what is the overall idea/strategy to use when applying recursion to a situation? I mean, how should I approach the problem? What aspects of the problem will be used as recursive criteria, etc?

Thanks!

Edit 6/29:

While I appreciate the 2 answers, I think maybe the preamble to my question was too long because it seems to be getting all of the attention. What I'm really asking is for someone to share with me, a person who "thinks" in loops, an approach for implementing recursive solutions. (For purposes of the question, please assume I have a sufficient understanding of the solution, but just need to create recursive code.) In other words, to apply a recursive solution, what am I looking for in the problem/solution that I will then use for the recursion? Maybe some very general statements about applying recursion would be helpful too. (note: please, not definitions of recursion, since I think I pretty much understand the definition. It's just the process of applying them I am asking about.) Thanks!

4

3 回答 3

4

每个循环都可以很容易地变成递归。（的确，每个递归都可以变成循环，但并不总是那么容易。）

但是，我意识到如果你不明白如何说“相当容易”实际上并不是很有帮助，所以这里的想法是：

对于这个解释，我将假设一个普通的 while 循环——没有嵌套循环或 for 循环，没有从循环中间跳出，没有从循环中间返回，等等。那些其他的东西也可以处理，但会混淆解释。

普通的 while 循环可能如下所示：

1. x = initial value;
2. while (some condition on x) {
3.     do something with x;
4.     x = next value;
5. }
6. final action;

那么递归版本将是

A. def Recursive(x) {
B.     if (some condition on x) {
C.         do something with x;
D.         Recursive(next value);
E.     }
F.     else { # base case = where the recursion stops
G.         final action;
H.     }
I.
J. Recursive(initial value);

所以，

  • 第 1 行中 x 的初始值成为第 J 行 Recursive 的原始参数
  • 第 2 行的循环条件变成了 B 行的 if 条件
  • 第 3 行循环内的第一个动作成为 C 行的 if 内的第一个动作
  • 第 4 行 x 的下一个值成为第 D 行 Recursive 的下一个参数
  • 第 6 行的最后一个动作变成了 G 行的基本情况下的动作

如果在循环中更新了多个变量，那么递归函数中通常会有相应数量的参数。

同样，可以修改这个基本配方以处理比普通的 while 循环更高级的情况。

次要评论：在递归函数中，将基本情况放在 if 的“then”一侧而不是“else”一侧会更常见。在这种情况下，您会将 if 的条件翻转为相反的条件。也就是说，while 循环中的条件测试何时继续执行，而递归函数中的条件测试何时停止。

于 2013-07-01T20:09:54.940 回答
2

我可能没有很好地解释它，但我认为我理解它，并且我可以跟踪/跟踪我见过的结构化示例

太酷了，如果我很好地理解了您的解释，那么乍一看您认为递归的工作方式是正确的。

我们的教授希望我们在每一个机会都递归地编写，并且已经做出了（技术上不准确的？）声明，所有循环都可以用递归替换

这不是不准确的。这是事实。反过来也是可能的：每次使用递归函数时，都可以使用迭代来重写。这可能很难且不直观（就像遍历一棵树），但这是可能的。

我怎样才能认识到循环可以/不能变成递归

简单的：

在此处输入图像描述

进行转换时使用的总体思路/策略是什么？

不幸的是，没有这样的事情。我的意思是没有通用或通用的“全力以赴”的方法，您必须在解决特定问题时专门考虑每种情况。然而，有一件事可能会有所帮助。从迭代算法转换为递归算法时，请考虑模式。仅以微小差异不断重复自身的部分究竟在多长时间和何处？

此外，如果您想将递归算法转换为迭代算法，请考虑在硬件级别实现递归的最流行的方法是使用（调用）堆栈。除非在求解诸如心爱的阶乘或斐波那契函数之类的简单可转换算法时，您始终可以考虑它在汇编程序中的外观，并创建一个显式堆栈。肮脏，但有效。

于 2013-06-28T19:47:44.490 回答
0 
for(int i = 0; i < 50; i++) 
{
    for(int j = 0; j < 60; j++)
    {
    }
}

等于：

rec1(int i)
{
    if(i < 50)
        return;
    rec2(0);
    rec1(i+1);
}

rec2(int j)
{
    if(j < 60)
        return;
    rec2(j + 1);
}

每个循环都可以是递归的。相信你的教授，他是对的！

于 2013-06-28T19:42:24.743 回答