python递归算法

递归是一种常见的解决问题的方法，即把问题逐渐简单化。递归的基本思想就是“自己调自己”，一个使用递归技术的方法将会直接或间接的调用自己。

利用递归可以用简单的程序来解决一些复杂的问题。比如：斐波那契数列的计算、汉诺塔、快排等问题。

递归机构包括两部分：

定义递归头。解答：什么时候不调用自身方法。如果没有头，将陷入死循环，也就是递归结束的条件。

递归体。解答：什么时候需要调用自身方法。

示例：

#使用递归求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))