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