如何以递归方式思考？

问题描述 投票：11回答：5

为了理解贪婪方法和动态编程等高级算法概念，首先需要精通递归。

我对递归比较新。每当提出问题时，首先要记住的是使用迭代的解决方案。即使我知道递归方法的含义及其工作方式，但很难以递归方式进行思考。

请回答以下问题，以帮助解决问题：

1）任何迭代方法都可以用递归代替，反之亦然吗？

例如，如何以递归方式打印大小为n的数组中的元素？

for i 0 to n
 Print a[i]

2）如何递归地解决问题？步骤是什么？是否有任何提示可以确定问题可以递归解决？

例如：如果要求打印出字符串的所有子字符串

INPUT: CAT
OUTPUT: CAT,CA,A,AT,T

我可以快速提出迭代方法。使用两个循环可以解决问题。

但递归地如何解决它。如何识别问题可以递归解决。

如果回答我的第一个问题是肯定的，使用两次递归而不是迭代可以解决我的问题？

3）任何人都可以建议我一些材料/资源来彻底理解递归的概念吗？

string algorithm recursion iteration tail-recursion
5个回答
7
投票
  1. 是的，主要是。一般来说，递归是为程序员而不是计算机进行的。迭代方法在某些情况下可能比递归方法运行得更快，但迭代方法可能需要300行代码和递归3.还有一些情况下，很容易弄清楚如何递归编程，但非常很难反复写，反之亦然。
  2. 通常，递归解决方案需要在功能方面。如果我们使用类似C ++的东西，我们可以使用处理字符串引用和事物的解决方案，慢慢调整作为参数传递的字符串。接近“两次递归”结束时的观点是错误的。这里的原则是，我们可以做一个递归方法，而不是两次迭代。
  3. http://introcs.cs.princeton.edu/java/23recursion/这个网站（谷歌搜索的高处）讲授了许多递归的数学理论，并包含一个常见问题解答，可能会给你一个更令人满意的答案。
14
投票

有一种思考递归的方法，使其像迭代一样简单。

在迭代中，我们有一个循环。可以认为它有4个部分：

  1. 基于某些“控制”数据继续或停止的决定被评估为逻辑条件。
  2. 工作完成的身体。有时，身体与下一部分结合在一起。
  3. 一种改变“控制”数据的方法。经常换柜台。
  4. 一种再次调用构造（在本例中为循环）的方法。在c风格的语言中，这是由for，while或do语法提供的。

在递归中，我们有一个函数（有时是几个）。他们有相同的4个部分：

  1. 基于某些“控制”数据继续或停止的决定被评估为逻辑条件。控制数据通常作为参数传递给函数。
  2. 工作完成的身体。有时，身体与下一部分结合在一起。
  3. 一种改变“控制”数据的方法。经常换柜台。
  4. 一种再次调用构造（在本例中为函数）的方法 - 这意味着调用函数（并记住传递更改的“控制”数据）。

两个构造具有相同的部分应该不足为奇，因为它们是等价的。

5
投票

我们来完成一项简单的任务吧。打印数字从1到10.我将在这里使用Python2.7。

for i in range(1,11):
    print i

现在让我们尝试使用递归来做同样的事情。

>>> def print_me(n):
    if n > 0:
        print_me(n - 1)
        print n
    else:
        return

>>> print_me(10)
1
2
3
4
5
6
7
8
9
10

那我们怎么想呢？

  • 第一步：想想我的界限。我需要两个。 1和10.接下来。
  • 第2步：打印声明。这是我们的动机。打印数字。我们希望它从1到10.所以我需要先打印1。
  • 第3步：我们首先编写一个函数来完成打印作为参数传递的数字的工作。让我们想一想，主要任务。 def print_me（n）：print n
  • 第4步：如果n <1，我希望函数返回。 def print_me（n）：如果n> 0：print n else：return
  • 第5步：现在我想将1到10之间的数字传递给这个函数，但是我们不需要1到10的循环，然后将它传递给我们的函数。我们希望它以递归方式完成。

什么是递归？简单来说，重复应用递归过程或定义。

所以为了使它递归，我们需要调用函数本身。我们希望通过1到10的范围。

def print_me(n):
    if n > 0:
        print_me(n - 1)
        print n
    else:
        return

总结：所有递归调用必须遵守3条重要规则：

  1. 递归算法，必须有一个基本案例。
  2. 递归算法，必须改变其状态并向基本情况移动。
  3. 递归算法必须递归地调用自身。

来源：interactivepython

Javascript中的另一个程序来寻找阶乘：

function factorial(n){
    if (n == 1)
        {
        return 1;
        }
    else {
        return n * factorial(n-1);
        }
}
0
投票
@Test
public void testStrings() {
   TreeSet<String> finalTree = getSubStringsOf("STACK");
    for(String subString : finalTree){
        System.out.println(subString);
    }
}

public TreeSet<String> getSubStringsOf(String stringIn) {
    TreeSet<String> stringOut = new TreeSet<String>();
    if (stringIn.length() == 1) {
        stringOut.add(stringIn);
        return stringOut;
    } else {
        for (int i = 1; i < stringIn.length() ; i++) {
            String stringBefore = stringIn.substring(0, i);
            String stringAfter = stringIn.substring(i);
            stringOut.add(stringBefore);
            stringOut.add(stringAfter);
            stringOut.addAll(getSubStringsOf(stringBefore));
            stringOut.addAll(getSubStringsOf(stringAfter));
        }
        return stringOut;
    }
}

我不知道你是否需要解释。每次可能的时候将字符串分成两部分。因此，Cat被分成CA，T和C，AT，您将它们添加到子字符串列表中，然后查找这些子字符串的每个子字符串。如果String是单个字符，则将单个字符添加到树中。

编辑：这是STACK的输出：

A AC ACK C CK K S ST STA STAC T TA TAC TACK

再次编辑：正如您所看到的，每次运行方法subString时，您将在其中使用它两次，除非它是单个字符String。因此复杂度为O（n²）。对于'STACK'，程序长0.200毫秒，因为“STACKSTACKSTACK”（3倍堆栈）是2秒，因为“STACKSTACKSTACKSTACKSTACK”理论上是2 ^ 10倍，因此是2000秒。

0
投票

这是我在Python中的简单测试：

def p(l, index):
    if index == len(l):
        return
    else:
        print l[index]
        index = index + 1
        p(l, index)

并致电：

p("123456", 0)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.