函數遞歸
- 一 函數遞歸調用介紹
- 二 回溯與遞推
一 函數遞歸調用介紹
函數不僅可以嵌套定義，還可以嵌套調用，即在調用一個函數的過程中，函數内部又調用另一個函數，而函數的遞歸調用指的是在調用一個函數的過程中又直接或間接地調用該函數本身
例如
在調用f1的過程中，又調用f1，這就是直接調用函數f1本身
def f1():
print('from f1')
f1()
f1()
在調用f1的過程中，又調用f2，而在調用f2的過程中又調用f1，這就是間接調用函數f1本身
def f1():
print('from f1')
f2()
def f2():
print('from f2')
f1()
f1()
從上圖可以看出，兩種情況下的遞歸調用都是一個無限循環的過程，但在python對函數的遞歸調用的深度做了限制，因而并不會像大家所想的那樣進入無限循環，會抛出異常，要避免出現這種情況，就必須讓遞歸調用在滿足某個特定條件下終止。
提示：
#1. 可以使用sys.getrecursionlimit()去檢視遞歸深度，預設值為1000，雖然可以使用
sys.setrecursionlimit()去設定該值，但仍受限于主機作業系統棧大小的限制
#2. python不是一門函數式程式設計語言，無法對遞歸進行尾遞歸優化。
二 回溯與遞推
下面我們用一個淺顯的例子，為了讓讀者闡釋遞歸的原理和使用：
例4.5
某公司四個員工坐在一起，問第四個人薪水，他說比第三個人多1000，問第三個人薪水，第他說比第二個人多1000，問第二個人薪水，他說比第一個人多1000，最後第一人說自己每月5000，請問第四個人的薪水是多少？
思路解析：
要知道第四個人的月薪，就必須知道第三個人的，第三個人的又取決于第二個人的，第二個人的又取決于第一個人的，而且每一個員工都比前一個多一千，數學表達式即：
salary(4)=salary(3)+1000
salary(3)=salary(2)+1000
salary(2)=salary(1)+1000
salary(1)=5000
總結為：
salary(n)=salary(n-1)+1000 (n>1)
salary(1)=5000 (n=1)
很明顯這是一個遞歸的過程，可以将該過程分為兩個階段：回溯和遞推。
在回溯階段，要求第n個員工的薪水，需要回溯得到(n-1)個員工的薪水，以此類推，直到得到第一個員工的薪水，此時，salary(1)已知，因而不必再向前回溯了。然後進入遞推階段：從第一個員工的薪水可以推算出第二個員工的薪水(6000)，從第二個員工的薪水可以推算出第三個員工的薪水(7000)，以此類推，一直推算出第第四個員工的薪水(8000)為止，遞歸結束。需要注意的一點是，遞歸一定要有一個結束條件，這裡n=1就是結束條件。
代碼實作：
def salary(n):
if n==1:
return 5000
return salary(n-1)+1000
s=salary(4)
print(s)
執行結果：
程式分析：
在未滿足n==1的條件時，一直進行遞歸調用，即一直回溯，見圖4.3的左半部分。而在滿足n==1的條件時，終止遞歸調用，即結束回溯，進而進入遞推階段，依次推導直到得到最終的結果。
遞歸本質就是在做重複的事情，是以理論上遞歸可以解決的問題循環也都可以解決，隻不過在某些情況下，使用遞歸會更容易實作，比如有一個嵌套多層的清單，要求列印出所有的元素，代碼實作如下
items=[[1,2],3,[4,[5,[6,7]]]]
def foo(items):
for i in items:
if isinstance(i,list): #滿足未周遊完items以及if判斷成立的條件時，一直進行遞歸調用
foo(i)
else:
print(i,end=' ')
foo(items) #列印結果1 2 3 4 5 6 7
使用遞歸，我們隻需要分析出要重複執行的代碼邏輯，然後提取進入下一次遞歸調用的條件或者說遞歸結束的條件即可，代碼實作起來簡潔清晰