我怎样才能build立一个Python的recursion函数?

我怎样才能build立一个Python的recursion函数?

我想知道你的意思是“recursion的”。 下面是计算阶乘函数的recursion函数的一个简单例子:

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

recursionalgorithm的两个关键要素是:

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

Python中的recursion就像其他语言的recursion一样工作,recursion结构本身就是定义的:

例如,recursion类可以是二叉树(或任何树):

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

如前所述,recursion结构必须具有终止条件。 在这个类中,它不是那么明显,因为只有在添加了新元素的情况下它才会recursion,而且只会增加一次。

另外值得注意的是,python在默认情况下对recursion的深度有一个限制,以避免吸收所有的计算机内存。 在我的电脑上,这是1000.我不知道这是否改变,取决于硬件等。要看到你的:

 import sys sys.getrecursionlimit() 

并设置它:

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

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

假设你想build立:u(n + 1)= f(u(n))和u(0)= u0

一个解决scheme是定义一个简单的recursion函数:

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

不幸的是,如果你想计算u的高值,你会遇到堆栈溢出错误。

另一个解决scheme是一个简单的循环

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

但是如果你想要n的不同值的多个值,这是不理想的。 您可以caching数组中的所有值,但可能会遇到内存不足错误。 您可能想要使用生成器:

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

还有很多其他的select,但我想这些是主要的。

recursion函数示例:

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

运行它:

 recursive("Hello world", 0)