什么是遞歸函數(shù)？
遞歸(recursion)：
1.是一個(gè)函數(shù)
2.函數(shù)執(zhí)行的過程中，自己調(diào)用自己
3.遞歸一定有結(jié)束調(diào)用自己的條件
4.遞歸效率不高
5.什么問題必須用遞歸？漢諾塔
6.不會(huì)死循環(huán)，有最大遞歸次數(shù)限制，會(huì)報(bào)錯(cuò) RecursionError: maximum recursion depth exceeded while calling a Python object

So，知道了什么是遞歸函數(shù)，直接上代碼看例子，以斐波那契數(shù)列（Fibonacci sequence）為例：
1 1 2 3 5 8 13 21 34
前兩項(xiàng)為1，后面每一項(xiàng)的值為其前兩項(xiàng)值的和
使用非遞歸算法求fib數(shù)列中第n項(xiàng)的值：

            
              def fib1(n):
    n1 = 1
    n2 = 1
    for i in range(n-2):
        n1,n2 = n2,n1+n2
    return n2

print(fib1(7))

            
          

使用遞歸算法求fib數(shù)列中第n項(xiàng)的值：

            
              def fib2(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib2(n-2)+fib2(n-1)

print(fib2(7))

            
          

剛接觸遞歸可能很難理解，可能看不懂代碼的實(shí)現(xiàn)邏輯，建議使用3次調(diào)用，來分析遞歸調(diào)用的過程。
以fib2(4)為例

            
              fib2(4)-->
fib2(3)+fib2(2) -->fib2(3)=fib2(2)+fib2(1),fib2(2)=1-->
fib2(2)+fib2(1)+1-->fib2(2)=1,fib2(1)=1-->
fib2(4) = (fib2(2)+fib2(1))+fib2(2)=1+1+1 = 3 

            
          

注：
遞歸的效率不高