day15:递归函数&递归练习题

# 1.一个简单的递归例子
def digui(n):
    print(n,"<====1===>")
    if n > 0:    
        digui(n-1<====2===>)
digui(5)

"""
# 代码解析:
去的过程:
n = 5 print(5,"<====1===>") 5>0 条件成立-> digui(5-1) => digui(4) 代码阻塞在第13行
n = 4 print(4,"<====1===>") 4>0 条件成立-> digui(4-1) => digui(3) 代码阻塞在第13行
n = 3 print(3,"<====1===>") 3>0 条件成立-> digui(3-1) => digui(2) 代码阻塞在第13行
n = 2 print(2,"<====1===>") 2>0 条件成立-> digui(2-1) => digui(1) 代码阻塞在第13行
n = 1 print(1,"<====1===>") 1>0 条件成立-> digui(1-1) => digui(0) 代码阻塞在第13行
n = 0 print(0,"<====1===>") 0>0 条件不成立 print(0,"<====2===>") 
当前这层空间代码已经执行结束
此刻触发回的过程

n = 1 从上一次13行的代码阻塞位置,继续向下执行 print(1,"<====2===>")
n = 2 从上一次13行的代码阻塞位置,继续向下执行 print(2,"<====2===>")
n = 3 从上一次13行的代码阻塞位置,继续向下执行 print(3,"<====2===>")
n = 4 从上一次13行的代码阻塞位置,继续向下执行 print(4,"<====2===>")
n = 5 从上一次13行的代码阻塞位置,继续向下执行 print(5,"<====2===>")
到此,递归函数彻底执行结束.
5 4 3 2 1 0 0 1 2 3 4 5

"""

 常规方法
# 5! = 5*4*3*2*1
 func(n):
    total = 1
    for i in range(n,-1):
        total *= i
    return total

res = func(5)
print(res)

 递归写法
 jiecheng(n):
    if n <= 1:
        return 1
    return n*jiecheng(n-1)
res = jiecheng(5(res)

return 后面的表达式,一定是先计算完在返回


# 代码解析:
# 去的过程:
n = 5   return 5*jiecheng(5-1) => 5 * jiecheng(4)
n = 4   return 4*jiecheng(4-1) => 4 * jiecheng(3)
n = 3   return 3*jiecheng(3-1) => 3 * jiecheng(2)
n = 2   return 2*jiecheng(2-1) => 2 * jiecheng(1)
n = 1   return 1

# 回的过程:
n = 2   return 2*jiecheng(2-1) => 2 * jiecheng(1) => 2 * 1
n = 3   return 3*jiecheng(3-1) => 3 * jiecheng(2) => 3 * 2 * 1
n = 4   return 4*jiecheng(4-1) => 4 * jiecheng(3) => 4 * 3 * 2 * 1
n = 5   return 5*jiecheng(5-1) => 5 * jiecheng(4) => 5 * 4 * 3 * 2 * 1
return 5 * 4 * 3 * 2 * 1 => return 120

额外解析:
jiecheng(1) => 1
jiecheng(2) => 2*jiecheng(1) => 2*1
jiecheng(3) => 3*jiecheng(2) => 3*2*1
jiecheng(4) => 4*jiecheng(3) => 4*3*2*1
jiecheng(5) => 5*jiecheng(4) => 5*4*3*2*1
"""

 jiecheng(n,endval):
     endval
    return jiecheng(n-1,endval*n)

res = jiecheng(5,1(res)




# 代码解析:
去的过程
n=5,endval=1         return jiecheng(5-1,endval*5) => jiecheng(4,1*5)
n=4,endval=1*5       return jiecheng(4-1,endval*4) => jiecheng(3,1*5*4)
n=3,endval=1*5*4     return jiecheng(3-1,endval*3) => jiecheng(2,1*5*4*3)
n=2,endval=1*5*4*3   return jiecheng(2-1,endval*2) => jiecheng(1,1*5*4*3*2)
n=1,endval=1*5*4*3*2 return 120

回的过程:
n=2 return 120
n=3 return 120
n=4 return 120
n=5 return 120

因为最后一层空间的返回值就是第一层空间的返回值,所有在使用尾递归的时候
不需要考虑回的逻辑过程,就能解决问题.推荐使用.
"""

 优化1
def jiecheng(n,endval=1):
    n)

res = jiecheng(5print(res,1)"><111>)


 优化2
为了避免用户乱传参数,把endval这个参数隐藏起来"""
 outer(n):
    ):
        :
             endval
        n)
        
    return jiecheng(n)  jiecheng(n-1,endval*n)

res = outer(5print(res)

 feb(n):
     递归跳出的条件
    if n <= 2:  n == 1 or n == 2 => 1
        return feb(n-1) + feb(n-2)
res = feb(5print(res)