如何在 python 中构建递归函数？[重复]

问题描述：

如何在 python 中创建递归函数？

解决方案 1：

我想知道你的意思是不是“递归”。下面是一个计算阶乘函数的递归函数的简单示例：

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

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

• 终止条件：n == 0

• 减少步骤中，函数每次使用较小的数字调用自身：factorial(n - 1)

解决方案 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()

编辑：我不能保证我的二叉树是有史以来最高效的设计。如果有人能改进它，我很乐意听听你的看法

解决方案 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

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

解决方案 4：

递归函数示例：

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

运行它：

recursive("Hello world", 0)