python的递归函数

admin管理员组

文章数量:1794759

python的递归函数

递归函数简单的定义：1、函数调用自身函数的行为。2、有一个正确的返回条件

python的递归函数有默认递归深度且可以设置

以下几个算法实例可以更好的理解递归函数的定义和使用场景

例1，一个求阶乘的函数，正整数阶乘指从1乘以2乘以3乘以4一直乘到所指定的数，以下为非递归与递归两种函数实现

#非递归函数方式 def notrecursion(n): num = n for i in range(1,n): num = num * i return num a = int(input("请输入：")) b = notrecursion(a) print(b) #递归函数方式 def recursion(n): if n == 1:# 正确的返回添加（结束条件） return 1 else: return n * recursion(n-1) #调用自身函数的行为 a = int(input("请输入：")) b = recursion(a) print(b)

通常情况下，递归函数会比普通循环迭代的效率低，占用内存更多。比如上面的阶乘函数例子。当然如果这个例子可能看太出来这个影响。我们可以再一个例子：

例2，斐波那契数列迭代实现

#非递归函数方式 def Fibonacci01(n): n1 = 1 n2 = 1 n3 = 1 if n < 1: print("error") return -1 while (n-2) > 0: n3 = n1 + n2 n1 = n2 n2 = n3 n = n - 1 return n3 a = Fibonacci01(3) if a != -1: print(a) #递归函数方式(用次方法，逻辑比较简单清晰，但是非常占用内存。) def Fibonacci02(n): if n < 1: print("error") return -1 if n == 1 or n == 2: return 1 else: return Fibonacci02(n-2) + Fibonacci02(n-1) a = Fibonacci02(3) if a != -1: print(a)

递归函数对于某些算法和事件处理起来是比较简单的，甚至如果循环迭代的方法还不一定能想出来。比如以下例子：

例3，汉若塔游戏解决算法（汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。）

#汉诺塔递归函数 def Hanoi(n,x,y,z): if n == 1: print(x ,"-->" ,z) else: Hanoi(n-1,x,z,y)# 将前n-1个盘子从x移动到y上 print(x ,"-->" ,z)# 将最底下的最后一个盘子从x移动到z上 Hanoi(n-1,y,x,z)# 将y上的n-1个盘子移动到z上 n = int(input("请输入层数：")) Hanoi(n,"x","y","z")

本文标签： 递归函数Python