递归函数

递归函数的理解与定义

递归函数是在函数内部调用自身的函数结构，它构成一个死循环，需要设置退出条件。

递归函数主要解决递推问题。

递归函数的关键是内存中的调用过程（前进，入栈）和计算过程（后退，出栈）。每次调用时，生成新的函数对象（内存入栈），直到满足退出条件时停止生成新函数对象并开始转入计算。每次计算时，依次结束满足条件的函数，后退（内存出栈），直到回到第一次调用为止。

例如，有一个递推函数

f(0)=0                       (n==0)
f(n)=n+f(n-1)                (n>=1)

示例程序如下

alist=[0,1,2,3,4,5]

# 普通函数，遍历数组并计算
def sumFun(alist):
    asum=0
    for i in range(len(alist)):
        asum=asum+alist[i]
    return asum

print(sumFun(alist))      # 15

# 递归函数的定义，里面隐含了循环过程
def sumFun2(n):
    if n==0:              # 当n==0时返回单个值，不再返回函数的调用，不再循环
        return 0
    asum=n+sumFun2(n-1)   # 当n>=1时返函数的调用，这个函数是自身，构成无限循环
    return asum

print(sumFun2(5))          # 15

事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

递归调用与计算过程分析

# 定义全局变量
i=0

# 递归函数的定义
def sumFun2(n):
    global i
    i=i+1
    # 记录递归前进信息（递进）
    print("第i次调用与对应的n值：",i,n)   
    if n==0:              # 当n==0时返回单个值，不再返回函数的调用，不再循环
        return 0
    asum=n+sumFun2(n-1)   # 当n>=1时返函数的调用，这个函数是自身，构成无限循环
    # 记录递归后退信息（回归）
    print("第i次调用与对应的n和asum：",i,n,asum)
    return asum

print(sumFun2(5))          # 15

运行结果

C:UsershccmaAnaconda3python.exe E:/wkp01/p00/test01/py001/t09.py
第i次调用与对应的n值： 1 5
第i次调用与对应的n值： 2 4
第i次调用与对应的n值： 3 3
第i次调用与对应的n值： 4 2
第i次调用与对应的n值： 5 1
第i次调用与对应的n值： 6 0
第i次调用与对应的n和asum： 6 1 1
第i次调用与对应的n和asum： 6 2 3
第i次调用与对应的n和asum： 6 3 6
第i次调用与对应的n和asum： 6 4 10
第i次调用与对应的n和asum： 6 5 15
15

Process finished with exit code 0

递归就是一种无限循环与控制。如果循环次数太多，会造成栈溢出，因为每次递进时会生成新的函数对象（内存大小有限）。