斐波那契_尾递归

悠悠 2021-11-13 18:50 313阅读 0赞

# (1)计算任意数n的阶乘
    # 5! 5*4*3*2*1
    # 8! 8*7*6*5*4*3*2*1
    '''
    递归函数通过两个条件出发回的过程:
    (1) 当前函数彻底执行完毕的时候,触发回的过程,回到上一层函数的调用处
    (2) 当前函数遇到return 返回值的时,触发回的过程,回到上一层函数的调用处
    '''
    
    # 普通方法
    n = 5
    total = 1
    for i in range(1,n+1):
    	total *= i
    print(total)
    
    # 5*4*3*2*1
    def jiecheng(n):
    	if n<=1 :
    		return 1
    	return n * jiecheng(n-1)
    
    # jiecheng(1) => 1
    res = jiecheng(5)
    print(res)
    '''
    # 代码解析:
    去的过程:
    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 * jiechneg(2)
    n = 2 return 2 * jiecheng(2-1) => 2 * jiecheng(1)
    n = 1 return 1
    
    回的过程:
    n = 2 return 2 * jiecheng(2-1) => 2 * 1
    n = 3 return 3 * jiecheng(3-1) => 3 *  2 * 1
    n = 4 return 4 * jiecheng(4-1) => 4 * 3 *  2 * 1
    n = 5 return 5 * jiecheng(5-1) => 5 *  4 * 3 *  2 * 1
    res =  5 *  4 * 3 *  2 * 1 =120
    '''
    
    
    # (2)尾递归: 只返回递归函数本身且非表达式(没有运算(+-*/..))
    '''
    只开辟一个栈帧空间完成递归函数(因为最终的返回值就是第一层空间的返回值,所以只需要一层栈帧空间即可,不停的进行替换)
    cpython解释器不支持.可以换一个支持尾递归的解释器(比如在公司内部大型服务器架构的解释器 推荐使用)
    '''
    # 方法一
    def jiecheng2(n,endval=1):
    	if n<=1 :
    		return endval
    	return jiecheng2(n-1,n*endval)
    res = jiecheng2(5,1)
    print(res)
    '''
    # 去的过程
    n=5 endval = 1
    	return jiecheng(5-1,5*1) => jiecheng(4,5*1)
    n=4 endval = 5*1
    	return jiecheng(4-1,4 *5*1) => jiecheng(3,4*5*1)
    n=3 endval = 4*5*1
    	return jiecheng(3-1,3*  4*5*1) => jiecheng(2, 3*4*5*1)
    n=2 endval = 3*4*5*1
    	return jiecheng(2-1,2*  3*4*5*1) => jiecheng(1, 2*3*4*5*1)
    n=1 endval = 2*3*4*5*1
    	n<=1 这个条件满足了 直接返回endval
    
    # 回的过程
    n=2 endval = 3*4*5*1
    	return jiecheng(2-1,2*  3*4*5*1) => 2*3*4*5*1
    n=3 endval = 4*5*1
    	return jiecheng(3-1,3*  4*5*1) => 2*3*4*5*1
    n=4 endval = 5*1
    	return jiecheng(4-1,4 *5*1) => 2*3*4*5*1
    n=5 endval = 1
    	return jiecheng(5-1,5*1) => 2*3*4*5*1
    	
    如果运行到最后一层函数,有返回值了,那么这个返回值就是最终的值,
    所有尾递归只需要一层栈帧空间.
    '''
    
    # 方法二 优化版
    # 系统底层用
    def jiecheng2(n,endval):
    	if n<=1 :
    		return endval
    	return jiecheng2(n-1,n*endval)
    # 给用户用 不需要用户填写第二个参数(比较人性化)
    def jiecheng3(n):
    	return jiecheng2(n,1)
    res = jiecheng3(5)
    print(res)
    
    # (3)斐波那契数列 
    # 1,1,2,3,5,8,13,21,34,55
    # 第n个数 它的数值是多少?
    
    # 除了前2个 ,后面每一个值都是上一个数 + 上上的数 两者之和
    def fib(n):
    	if n ==1 or n==2:
    		return 1
    		
    	return fib(n-1) + fib(n-2)
    res = fib(5)
    print(res)
    
    '''
    代码解析:
    n = 5
    => return fib(5-1) + fib(5-2)
    => return fib(4) + fib(3) => 3 + 2 => 5
    fib(4) => 3
    fib(3)            +           fib(2)
    fib(2)+fib(1)=1+1=2       + 1
    2+1 = 3
    
    
    fib(3) =>2
    fib(2) + fib(1)
    1 + 1 = 2
    
    '''

转载于:https://www.cnblogs.com/huangjiangyong/p/10906561.html