递归是一种常见的解决问题的方法,即把问题逐渐简单化。递归的基本思想就是“自己调自己”,一个使用递归技术的方法将会直接或间接的调用自己。
利用递归可以用简单的程序来解决一些复杂的问题。比如:斐波那契数列的计算、汉诺塔、快排等问题。
递归机构包括两部分:
定义递归头。解答:什么时候不调用自身方法。如果没有头,将陷入死循环,也就是递归结束的条件。
递归体。解答:什么时候需要调用自身方法。
示例:
#使用递归求n!
def factorial(n):
if n == 1:
return n
else:
return n*factorial(n-1)
print(factorial(5))
#使用递归打印所以的文件和目录的路径
allPaths = []
def getAllFiles(path, level):
global allPaths
childPaths = os.listdir(path)
for child in childPaths:
childpath = os.path.join(path,child)
if os.path.isdir(childpath):
getAllFiles(childpath, level+1)
allPaths.append('\t'*level+childpath)
getAllFiles(r'D:\data', 0)
for i in reversed(allPaths):
print(i)
示例:斐波那契数列
#斐波那契数列(Fibonacci sequence),又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……。
#在数学上,费波那契数列是以递归的方法来定义:
#F0 = 0 (n=0)
#F1 = 1 (n=1)
#Fn = F[n-1]+ F[n-2](n=>2)
#方法一:循环
def feib1(n):
fbList = []
if n == 0:
fbList.append(0)
elif n == 1:
fbList.append(0)
fbList.append(1)
else:
fbList = [0,1]
for i in range(2,n+1):
fbList.append(fbList[i-1]+fbList[i-2])
return fbList
print(feib1(10))
#方法二:递归
def feib2(n):
if n==0:
return 0
elif n==1 or n==2:
return 1
return feib2(n-1)+feib2(n-2)
print(feib2(10))