如何在 python 中构建递归函数?
sddaf ads
问问题
180458 次
4 回答
81
我想知道您是否指的是“递归”。这是计算阶乘函数的递归函数的简单示例:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
递归算法的两个关键要素是:
- 终止条件:
n == 0
- 函数每次以较小的数字调用自身的缩减步骤:
factorial(n - 1)
于 2009-01-26T10:28:57.120 回答
10
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()
编辑:我不能保证我的二叉树是有史以来最有效的设计。如果有人可以改进它,我很高兴听到如何
于 2009-01-26T19:25:42.373 回答
5
假设您要构建: u(n+1)=f(u(n)) with 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
但是,如果您想要多个 u 值用于不同的 n 值,则这是次优的。您可以将所有值缓存在一个数组中,但您可能会遇到内存不足错误。您可能想改用生成器:
def u(n):
ux = u0
for i in xrange(n):
ux=f(ux)
yield ux
for val in u(1000):
print val
还有很多其他选择,但我想这些是主要的。
于 2009-01-26T10:35:04.520 回答
2
递归函数示例:
def recursive(string, num):
print "#%s - %s" % (string, num)
recursive(string, num+1)
运行它:
recursive("Hello world", 0)
于 2009-01-26T17:07:15.447 回答