如何以递归方式思考？

Question

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

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

请回答以下问题,以帮助解决问题:

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

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

for i 0 to n
 Print a[i]

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

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

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

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

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

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

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

Answer 1

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

在迭代中,我们有一个循环.可以认为它有4个部分:

在递归中,我们有一个函数(有时是几个).他们有相同的4个部分:

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

Answer 2

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

Answer 3

我们来完成一项简单的任务吧.打印数字从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的范围.

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

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

来源:interactivepython

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

function factorial(n){
    if (n == 1)
        {
        return 1;
        }
    else {
        return n * factorial(n-1);
        }
}