# ### 遞歸函數(shù)
"""
遞歸函數(shù) : 自己調(diào)用自己的函數(shù) , 叫做遞歸函數(shù)
遞 : 去
歸 : 回
一去一回叫做遞歸
"""
def digui(n):
    print(n,"<==1==>")
    if n > 0:
        digui(n-1)
    print(n,"<==2==>")
digui(5)
"""
# 去的過(guò)程
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==>") 到此最后一層函數(shù)空間徹底執(zhí)行完畢
# 回的過(guò)程
回到上一層函數(shù)空間  n = 1 代碼在第12行的位置,繼續(xù)往下執(zhí)行  print(1,"<==2==>")
回到上一層函數(shù)空間  n = 2 代碼在第12行的位置,繼續(xù)往下執(zhí)行  print(2,"<==2==>")
回到上一層函數(shù)空間  n = 3 代碼在第12行的位置,繼續(xù)往下執(zhí)行  print(3,"<==2==>")
回到上一層函數(shù)空間  n = 4 代碼在第12行的位置,繼續(xù)往下執(zhí)行  print(4,"<==2==>")
回到上一層函數(shù)空間  n = 5 代碼在第12行的位置,繼續(xù)往下執(zhí)行  print(5,"<==2==>")
到此遞歸函數(shù)執(zhí)行結(jié)束..
打印 543210012345
"""
"""
每次調(diào)用函數(shù)時(shí),都要單獨(dú)在內(nèi)存當(dāng)中開(kāi)辟空間,叫做棧幀空間,以運(yùn)行函數(shù)中的代碼
遞歸總結(jié):
	(1)遞歸實(shí)際上是不停的開(kāi)辟棧幀空間和釋放棧幀空間的過(guò)程,開(kāi)辟就是去的過(guò)程,釋放就是回的過(guò)程
	(2)遞歸什么時(shí)候觸發(fā)歸的過(guò)程:
		1.當(dāng)最后一層棧幀空間執(zhí)行結(jié)束的時(shí)候,觸發(fā)歸的過(guò)程.
		2.當(dāng)遇到return返回值的時(shí)候終止當(dāng)前函數(shù),觸發(fā)歸的過(guò)程.
	(3)遞歸不能無(wú)限的去開(kāi)辟空間,可能造成內(nèi)存溢出,藍(lán)屏死機(jī)的情況,所以一定要給予跳出的條件(如果遞歸的層數(shù)太大,不推薦使用)
	(4)開(kāi)辟的一個(gè)個(gè)棧幀空間,數(shù)據(jù)是彼此獨(dú)立不共享的.
"""
# 遞歸不能不限開(kāi)辟空間
"""官方說(shuō)法最大默認(rèn)是1000層."""
def deepfunc():
	deepfunc()
deepfunc()

# ### 1.使用遞歸實(shí)現(xiàn)任意數(shù)n的階乘 
# 普通實(shí)現(xiàn)
# 5! =5 *4*3*2*1
n = 5
total = 1
for i in range(n,0,-1):
	total *= i
print(total) # 120
# 遞歸實(shí)現(xiàn)
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))
"""
代碼解析:
去的過(guò)程:
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
回的過(guò)程:
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
到此程序結(jié)束:
返回  1 * 2 * 3 * 4 * 5
"""
print("<====================>")
# ### 2. 使用尾遞歸來(lái)實(shí)現(xiàn)任意數(shù)的階乘
""" return 在哪調(diào)用,在哪返回 """
"""自己調(diào)用自己,且返回時(shí)非運(yùn)算表達(dá)式,只是函數(shù)本身"""
"""
特點(diǎn):
	尾遞歸只開(kāi)辟一個(gè)空間,不會(huì)無(wú)限的開(kāi)辟,在一個(gè)空間里面去計(jì)算最后的結(jié)果進(jìn)行返回,比較節(jié)省空間,有的解釋器支持尾遞歸的調(diào)用特點(diǎn)
	但是cpython解釋器目前不支持
寫法:
	所有運(yùn)算的值都在函數(shù)的參數(shù)中計(jì)算完畢,最后返回運(yùn)算的參數(shù);
"""
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)
"""
代碼解析:
去的過(guò)程
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
最下層和最上層返回的結(jié)果是一致的,所以對(duì)于尾遞歸來(lái)說(shuō),只需要考慮去的過(guò)程,無(wú)需考慮回的過(guò)程即可完成;
"""
# 優(yōu)化代碼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>")
# 優(yōu)化代碼2 [把尾遞歸需要的參數(shù)值隱藏起來(lái),避免篡改.]
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))
# 優(yōu)化代碼3(擴(kuò)展)
# 閉包實(shí)現(xiàn)
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.使用遞歸來(lái)完成斐波那契數(shù)列
""" 1 1 2 3 5 8 13 21 34 ... """
def feib(n):
	if n == 1 or n == 2:
		return 1
	# 上一個(gè)結(jié)果 + 上上個(gè)結(jié)果
	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.可滑動(dòng)的序列 自定義一個(gè)函數(shù) 根據(jù)參數(shù)n的值 , 變成對(duì)應(yīng)個(gè)元素的容器 （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)
# 把里面的元組強(qiáng)轉(zhuǎn)成列表
print(list(map(list,it)))
# 2.青蛙跳臺(tái)階  (遞歸實(shí)現(xiàn))
'''
一只青蛙要跳上n層高的臺(tái)階
一次能跳一級(jí),也可以跳兩級(jí)
請(qǐng)問(wèn)這只青蛙有多少種跳上這個(gè)n層高臺(tái)階的方法?
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.遞歸反轉(zhuǎn)字符串 "將14235 反轉(zhuǎn)成53241" (遞歸實(shí)現(xiàn))
# 把后面的字符往前挪動(dòng) 方法一
strvar = "14235"
# lst.append(5)
# lst.append(3)
# lst.append(2)
# lst.append(4)
# lst.append(1)
# lth = 字符串的總長(zhǎng)度  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))
# 簡(jiǎn)寫
def func(lth,lst=[]):
	if lth == 0:
		return "".join(lst)
	res = strvar[lth-1]
	lst.append(res)
	return func(lth-1)
print(func(lth))
# 把前面的字符往后挪動(dòng) 方法二
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.斐波那契數(shù)列用尾遞歸實(shí)現(xiàn)
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))