有没有好的递归教程？使用Python语言？

Question

请问有没有人能指点我一下好的递归教程。我学过数据结构课程，其中涉及到递归，但是现在有点生疏了。想要复习一下递归...有什么建议吗？

- TopChef

---

关于递归教程的Stack Overflow问题：是否有Python的好的递归教程？ - Mark Rushakoff

真是太棒了，你先到了那里，马克！ :) - j_random_hacker

这太棒了，本应该是我的！ - Brent Writes Code

哎呀，我怎么能指望有一个递归问题而没有一个经典的自我链接笑话呢！:P - Jesse Emond

如果它能出现在右侧的“已链接”部分就好了 :/ - Mark Rushakoff

Answer 1

考虑这个问题。

更加严谨地说...

递归是解决具有明确定义基本情况的问题的一种方法（或者有多个基本情况，但为了简单起见，我只保留一个）。

例如，通常引用的阶乘问题是一个很好的例子。

阶乘做什么？让我们看一些例子：

factorial(0) = 1
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24

一个数的阶乘是它与它前面的数的阶乘的积，除非（现在，这就是基本情况）该数为0。0的阶乘为1。（你不能计算负数的阶乘，只能计算正整数的阶乘。）

因此，我们有了明确定义的基本情况。而且我们知道如何处理不是基本情况的数字（我们将它们乘以比它小1的数的阶乘）。现在我们已经准备好写我们的函数了。

def factorial(x):
    if x == 0:            # this is our base case
        return 1          # and this is what we do when we see it
    else:                 # this is what we do with all other numbers
        return x * factorial(x-1)

所以您需要：

1. 明确定义基本情况。
2. 找到一种方法，将非基本情况的问题减少到基本情况。

3. 在一个函数中正式表达这一点（当它很简单时！）如下：

   function:
       if base case: 
           this
       else: 
           something + function(something closer to the base case)
   

   如果你想要更高级的东西，谷歌有很多相关信息。

- Isaac

---

+1 对于递归答案 :-) 而且它也很好，而且是递归的！ - eruciform

Answer 2

我强烈推荐观看麻省理工学院的编程入门课程。 第四讲讨论递归。

- advait