如何在Python中编写递归函数？

Question

如何在Python中构建递归函数？

- sddaf ads

---

递归等同于递归。http://zh.wikipedia.org/wiki/递归关系 - S.Lott

Answer 1

我想知道您是否是指“递归”。这里有一个计算阶乘函数的简单递归函数示例：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

递归算法的两个关键要素是：

• 终止条件：n == 0
• 规模缩小，每次函数调用自身并传入较小的数字：factorial(n - 1)

- Greg Hewgill

---

一个旁注：并非所有的函数都必须停止才能发挥作用。例如，itertools.count()。顺便说一句，它可以通过递归实现。 - jfs

这里有一个问题。如果我让一个函数在 n 是偶数时进行乘法运算，而在 n 是奇数时让另一个函数进行乘法运算，那会发生什么呢？这两个函数显然会互相调用。假设我能最初调用正确的偶数或奇数函数，那会发生什么？ def even(n): return n*odd(n-1) def odd(n): if n==1: return 1 else: return n*even(n-1) - ffledgling

@Ayos：假设你的函数实现正确，那也可以正常工作。这种情况被称为互递归函数。 - Greg Hewgill

@GregHewgill，我似乎因为递归深度超过最大值而出现了RuntimeError，尽管我知道这不是无限递归。 - ffledgling

那么，递归深度有多深呢？Python 的默认递归深度限制是 5000 或者其他数值。 - Greg Hewgill

但是，这些条件都不是函数递归的必要条件。 - Grozz

Answer 2

在Python中，递归的工作方式与其他语言中的递归相同，递归结构是以自身为基础定义的：

例如，递归类可以是二叉树（或任何树）：

class tree():
    def __init__(self):
        '''Initialise the tree'''
        self.Data = None
        self.Count = 0
        self.LeftSubtree = None
        self.RightSubtree = None

    def Insert(self, data):
        '''Add an item of data to the tree'''
        if self.Data == None:
            self.Data = data
            self.Count += 1
        elif data < self.Data:
            if self.LeftSubtree == None:
                # tree is a recurive class definition
                self.LeftSubtree = tree()
            # Insert is a recursive function
            self.LeftSubtree.Insert(data)
        elif data == self.Data:
            self.Count += 1
        elif data > self.Data:
            if self.RightSubtree == None:
                self.RightSubtree = tree()
            self.RightSubtree.Insert(data)

if __name__ == '__main__':
    T = tree()
    # The root node
    T.Insert('b')
    # Will be put into the left subtree
    T.Insert('a')
    # Will be put into the right subtree
    T.Insert('c')

正如已经提到的，递归结构必须有一个终止条件。在这个类中，这并不是很明显，因为它只在添加新元素时进行递归，并且只多做一次。

值得注意的是，默认情况下Python有一个递归深度限制，以避免吸收计算机的所有内存。在我的电脑上，这个限制是1000。我不知道这是否会因硬件等原因而改变。要查看您的限制：

import sys
sys.getrecursionlimit()

并设置它：

import sys #(if you haven't already)
sys.setrecursionlimit()

编辑：我不能保证我的二叉树是最高效的设计。如果有人能够改进它，我很乐意听取建议。

- dangerouslyfacetious

Answer 3

假设您想要构建： u(n+1)=f(u(n))，其中u(0)=u0

一个解决方法是定义一个简单的递归函数：

u0 = ...

def f(x):
  ...

def u(n):
  if n==0: return u0
  return f(u(n-1))

很遗憾，如果您想计算较高的u值，您将遇到堆栈溢出错误。

另一个解决方案是使用简单的循环：

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  return ux

但是，如果你想为不同的n值获得多个u值，则这种方法并不理想。你可以将所有的值缓存到一个数组中，但是可能会遇到内存不足的错误。你可以考虑使用生成器代替：

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  yield ux

for val in u(1000):
  print val

还有很多其他选项，但我猜这些是主要的。

- MiniQuark

---

原始问题中说的是“recurrent”而不是“recursive”，因此我的答案现在已经没有太大意义，因为问题已经被修改。 - MiniQuark

有趣的回答，但我不明白最后一个例子的重点。 - lajarre

Answer 4

递归函数示例：

def recursive(string, num):
    print "#%s - %s" % (string, num)
    recursive(string, num+1)

使用以下方式运行：

recursive("Hello world", 0)

- Evan Fosmark

---

这个递归函数是如何结束/退出的？ - Ketan Maheshwari

真的。即使我很好奇，这会以什么样的方式结束？根据我的知识，在每次递归中都应该有一个平凡的语句。 - Nagaraj Tantri

如果没有限制递归深度的语句，程序会以 RuntimeError: maximum recursion depth exceeded 结束。 - Emanuel Ey

最大递归深度可以通过代码进行检查。import sys; sys.getrecursionlimit()。在我的系统上，它是1000。因此，这将运行1000次，然后停止。递归应该有两个要素，即退出条件和上升或下降。 - thuyein