# ### 递归函数

"""
递归函数 : 自己调用自己的函数 , 叫做递归函数
递 : 去
归 : 回
一去一回叫做递归
"""

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    
"""

递归流程图