Python全棧之遞歸函數

# ### 遞歸函數
"""
遞歸函數 : 自己調用自己的函數 , 叫做遞歸函數
遞 : 去
歸 : 回
一去一回叫做遞歸
"""
def digui(n):
    print(n,"<==1==>")
    if n > 0:
        digui(n-1)
    print(n,"<==2==>")
digui(5)
"""
# 去的過程
n = 5 print(5,"<==1==>")  if 5 > 0:   digui(5-1) =>  digui(4) 代碼阻塞在第12行
n = 4 print(4,"<==1==>")  if 4 > 0:   digui(4-1) =>  digui(3) 代碼阻塞在第12行
n = 3 print(3,"<==1==>")  if 3 > 0:   digui(3-1) =>  digui(2) 代碼阻塞在第12行
n = 2 print(2,"<==1==>")  if 2 > 0:   digui(2-1) =>  digui(1) 代碼阻塞在第12行
n = 1 print(1,"<==1==>")  if 1 > 0:   digui(1-1) =>  digui(0) 代碼阻塞在第12行
n = 0 print(0,"<==1==>")  if 0 > 0: 不成立 print(0,"<==2==>") 到此最後一層函數空間徹底執行完畢
# 回的過程
回到上一層函數空間  n = 1 代碼在第12行的位置,繼續往下執行  print(1,"<==2==>")
回到上一層函數空間  n = 2 代碼在第12行的位置,繼續往下執行  print(2,"<==2==>")
回到上一層函數空間  n = 3 代碼在第12行的位置,繼續往下執行  print(3,"<==2==>")
回到上一層函數空間  n = 4 代碼在第12行的位置,繼續往下執行  print(4,"<==2==>")
回到上一層函數空間  n = 5 代碼在第12行的位置,繼續往下執行  print(5,"<==2==>")
到此遞歸函數執行結束..
打印 543210012345
"""
"""
每次調用函數時,都要單獨在內存當中開辟空間,叫做棧幀空間,以運行函數中的代碼
遞歸總結:
	(1)遞歸實際上是不停的開辟棧幀空間和釋放棧幀空間的過程,開辟就是去的過程,釋放就是回的過程
	(2)遞歸什麼時候觸發歸的過程:
		1.當最後一層棧幀空間執行結束的時候,觸發歸的過程.
		2.當遇到return返回值的時候終止當前函數,觸發歸的過程.
	(3)遞歸不能無限的去開辟空間,可能造成內存溢出,藍屏死機的情況,所以一定要給予跳出的條件(如果遞歸的層數太大,不推薦使用)
	(4)開辟的一個個棧幀空間,數據是彼此獨立不共享的.
"""
# 遞歸不能不限開辟空間
"""官方說法最大默認是1000層."""
def deepfunc():
	deepfunc()
deepfunc()

# ### 1.使用遞歸實現任意數n的階乘 
# 普通實現
# 5! =5 *4*3*2*1
n = 5
total = 1
for i in range(n,0,-1):
	total *= i
print(total) # 120
# 遞歸實現
def jiecheng(n):
	if n <= 1:
		return 1
	return jiecheng(n-1) * n
print(jiecheng(2))
# jiecheng(1) => 1 
# jiecheng(2) => jiecheng(1) * 2 => 1 * 2
# jiecheng(3) => jiecheng(2) * 3 => 1 * 2 * 3
# jiecheng(4) => jiecheng(3) * 4 => 1 * 2 * 3 * 4
# jiecheng(5) => jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5
print(jiecheng(5))
"""
代碼解析:
去的過程:
n = 5 return jiecheng(n-1) * n => jiecheng(4) * 5
n = 4 return jiecheng(n-1) * n => jiecheng(3) * 4
n = 3 return jiecheng(n-1) * n => jiecheng(2) * 3
n = 2 return jiecheng(n-1) * n => jiecheng(1) * 2
n = 1 return 1
回的過程:
n = 2 return jiecheng(1) * 2 => 1 * 2
n = 3 return jiecheng(2) * 3 => 1 * 2 * 3
n = 4 return jiecheng(3) * 4 => 1 * 2 * 3 * 4
n = 5 return jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5
到此程序結束:
返回  1 * 2 * 3 * 4 * 5
"""
print("<====================>")
# ### 2. 使用尾遞歸來實現任意數的階乘
""" return 在哪調用,在哪返回 """
"""自己調用自己,且返回時非運算表達式,隻是函數本身"""
"""
特點:
	尾遞歸隻開辟一個空間,不會無限的開辟,在一個空間裡面去計算最後的結果進行返回,比較節省空間,有的解釋器支持尾遞歸的調用特點
	但是cpython解釋器目前不支持
寫法:
	所有運算的值都在函數的參數中計算完畢,最後返回運算的參數;
"""
def jiecheng(n,endval):
	if n <= 1:
		return endval
	return jiecheng(n-1 , n * endval)
res = jiecheng(5,1) # 5*4*3*2*1
print(res)
"""
代碼解析:
去的過程
n = 5 ,endval = 1 return jiecheng(n-1 , n * endval) => jiecheng(4,5*1) => 5*1*4*3*2
n = 4 ,endval = 5*1 return jiecheng(n-1 , n * endval) => jiecheng(3,5*1*4) => 5*1*4*3*2 
n = 3 ,endval = 5*1*4 return jiecheng(n-1 , n * endval) => jiecheng(2,5*1*4*3) => 5*1*4*3*2 
n = 2 ,endval = 5*1*4*3 return jiecheng(n-1 , n * endval) => jiecheng(1,5*1*4*3*2) => 5*1*4*3*2 
n = 1 ,endval = 5*1*4*3*2   if n <= 1 成立  return endval
endval = 5*1*4*3*2 
最下層空間的返回值 是 5*4*3*2*1  最上層接收到的返回值也是 5*4*3*2*1
最下層和最上層返回的結果是一致的,所以對於尾遞歸來說,隻需要考慮去的過程,無需考慮回的過程即可完成;
"""
# 優化代碼1
def jiecheng(n,endval=1):
	if n <= 1:
		return endval
	return jiecheng(n-1 , n * endval)
res = jiecheng(5,100) # 5*4*3*2*1
print(res,"<00000>")
# 優化代碼2 [把尾遞歸需要的參數值隱藏起來,避免篡改.]
def outer(n):
	def jiecheng(n,endval=1):
		if n <= 1:
			return endval
		return jiecheng(n-1 , n * endval)
	return jiecheng(n,1)# 120
print(outer(5))
# 優化代碼3(擴展)
# 閉包實現
def outer(n):
	endval = 1
	def jiecheng(n):
		nonlocal endval
		if n <= 1:
			return endval
		endval *= n 
		return jiecheng(n-1)
	return jiecheng
func = outer(5)
print(func(5),"<===111==>")
print("<================>")
# ### 3.使用遞歸來完成斐波那契數列
""" 1 1 2 3 5 8 13 21 34 ... """
def feib(n):
	if n == 1 or n == 2:
		return 1
	# 上一個結果 + 上上個結果
	return feib(n-1) + feib(n-2)
print(feib(5))
"""
# 代碼解析:
n = 5               feib(5) => 3 + 2 => return 5  
		feib(4)        +         feib(3)
    feib(3)+feib(2)          feib(2)+feib(1) => 1 + 1 => 2
feib(2)+feib(1)+feib(2) => 1 + 1 + 1 => 3    
"""

# (選做)
# 1.可滑動的序列 自定義一個函數 根據參數n的值 , 變成對應個元素的容器 （zip）
"""
listvar = [1,2,3,4,5,6,7,8,9]
n = 2
listvar = [[1,2],[3,4],[5,6],[7,8]]
n = 3
listvar = [[1,2,3],[4,5,6],[7,8,9]]
n = 4
listvar = [[1,2,3,4],[5,6,7,8]]
"""
"""
lst1 = [1,3,5,7,9]
lst2 = [2,4,6,8]
zip(lst1,lst2)
"""
listvar = [1,2,3,4,5,6,7,8,9]
n = 2
lst1 = [1,3,5,7,9]
lst2 = [2,4,6,8]
# lst1 = listvar[0::2]  <=> [1,3,5,7,9]
# lst2 = listvar[1::2]  <=> [2,4,6,8]
print(lst2,"1111")
print(list( zip(lst1,lst2) ))
n = 3
lst1 = [1,4,7]
lst2 = [2,5,8]
lst3 = [3,6,9]
# lst1 = listvar[0::3]  <=> [1,4,7]
# lst2 = listvar[1::3]  <=> [2,5,8]
# lst3 = listvar[2::3]  <=> [3,6,9]
print(lst1,"2222")
print(list( zip(lst1,lst2,lst3) ))
n = 4
lst1 = [1,5]
lst2 = [2,6]
lst3 = [3,7]
lst4 = [4,8]
# lst1 = listvar[0::4]  <=> [1,5,9]
# lst2 = listvar[1::4]  <=> [2,6]
# lst3 = listvar[2::4]  <=> [3,7]
# lst4 = listvar[3::4]  <=> [4,8]
print(lst1,"3333")
print(list( zip(lst1,lst2,lst3,lst4) ))
print("<=============>")
n = 3
lst = [ listvar[i::n] for i in range(n) ]
print(lst) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# zip(*lst) => zip([1,4,7],[2,5,8],[3,6,9])
it = zip(*lst)
print(list(it))
func = lambda n : zip(  *[ listvar[i::n] for i in range(n) ]   )
it = func(2)
# 把裡面的元組強轉成列表
print(list(map(list,it)))
# 2.青蛙跳臺階  (遞歸實現)
'''
一隻青蛙要跳上n層高的臺階
一次能跳一級,也可以跳兩級
請問這隻青蛙有多少種跳上這個n層高臺階的方法?
n = 1   1 => 1
n = 2   2 => 1 1 | 2
n = 3   3 => 1 1 1 | 1 2 | 2 1 
n = 4   5 => 1 1 1 1 | 1 2 1 | 2 1 1 | 1 1 2 | 2 2
n = 5   8 => 1 1 1 1 1 | 1 1 1 2 |2 1 1 1 | 1 2 1 1  | 1 1 2 1 | 2 2 1 | 1 2 2 | 2 1 2 
'''
def func(n):
	if n == 1 or n == 2:
		return n
	return func(n-1) + func(n-2)
print(func(5))
# 3.遞歸反轉字符串 "將14235 反轉成53241" (遞歸實現)
# 把後面的字符往前挪動 方法一
strvar = "14235"
# lst.append(5)
# lst.append(3)
# lst.append(2)
# lst.append(4)
# lst.append(1)
# lth = 字符串的總長度  lst 要插入的列表
def func(lth,lst=[]):
	if lth == 0:
		return lst
	res = strvar[lth-1]
	lst.append(res)
	return func(lth-1)
lth = len(strvar)
lst = func(lth)
print(lst) # ['5', '3', '2', '4', '1']
print("".join(lst))
# 簡寫
def func(lth,lst=[]):
	if lth == 0:
		return "".join(lst)
	res = strvar[lth-1]
	lst.append(res)
	return func(lth-1)
print(func(lth))
# 把前面的字符往後挪動 方法二
strvar = "14235"
def func(strvar):
	if len(strvar) == 1:
		return strvar
	return func(strvar[1:])+strvar[0]
res = func(strvar)
print(res)
"""
遞:
return func(4235) + 1
return func(235)  + 4
return func(35)   + 2
return func(5)    + 3
return 5
歸:
return func(5)    + 3 => 5 + 3
return func(35)   + 2 => 5 + 3 + 2
return func(235)  + 4 => 5 + 3 + 2 + 4
return func(4235) + 1 => 5 + 3 + 2 + 4 + 1
return 5 + 3 + 2 + 4 + 1
"""

# 4.斐波那契數列用尾遞歸實現
a,b = 0,1
i = 0
n = 5
while i < n:
	print(b)
	a,b = b,a+b
	i +=1
a,b = 0,1
n = 5
while n > 0:
	print(b)
	a,b = b,a+b
	n -= 1
print("<==============>")
def func(n,a=0,b=1):
	if n == 1:
		return b
	return func(n-1,b,a+b)
print(func(6))