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

Question

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

Answer 1

我想知道你是否意味着"递归".以下是计算阶乘函数的递归函数的简单示例:

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

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

• 终止条件: n == 0
• 减少步骤,函数每次调用自身的数字较小: factorial(n - 1)

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()

编辑:我不能保证我的二叉树是有史以来最有效的设计.如果有人能改进它,我会很高兴听到如何

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

还有很多其他选择,但我猜这些是主要的选择.