• 周一. 4月 22nd, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Python

admin

11月 28, 2021

什么是递归?

程序调用自身的编程技巧称为递归(recursion),递归说通俗一点,就是自己调用自己。

举例子:举个网上的例子

一个小朋友坐在第10排,他的作业本被小组长拿到了第1排,小朋友要拿回他的作业本,可以怎么办?他可以拍拍第9排小朋友,说:“帮我拿第1排的本子”,而第9排的小朋友可以拍拍第8排小朋友,说:“帮我拿第1排的本子”…如此下去,消息终于传到了第1排小朋友那里,于是他把本子递给第2排,第2排又递给第3排…终于,本子到手啦!这就是递归,拍拍小朋友的背可以类比函数调用,而小朋友们都记得要传消息、送本子,是因为他们有记忆力,这可以类比栈。

一、阶乘运算

实现阶乘运算: n…5x4x3x2x1

'''
n...5*4*3*2*1

n*(n-1)
'''

def fac(n):
    if n==1:
        return 1
    else:
        return n*fac(n-1)

print(fac(4))

'''
代码运行过程:
n = 4, 运行这行代码   return n*fab(n-1) --> 4*fac(3), 接着调用自身函数 fac()
n = 3, 运行这行代码   return n*fab(n-1) --> 4*3*fac(2), 接着调用自身函数 fac()
n = 2, 运行这行代码   return n*fab(n-1) --> 4*3*2fac(1), 接着调用自身函数 fac()
n = 1,  fac(1)=1  --> 4*3*2fac(1) --> 4*3*2*1
''' 

使用递归需要注意的点:

  1. 必须要有结束条件,不然就会进入死循环
  2. 每次进入更深一层递归时,问题规模(计算量)相比上次递归都应有所减少
  3. 递归执行效率不高,递归层次过多会导致栈溢出,所以使用递归的时候要注意

二、斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……

查找规律:
f(1)=1
f(2)=1

f(n)=f(n-1)+f(n-2) n >3

代码:

def fib(n):
    ''' 斐波那契数列 '''
    if n <= 2:
        ''' 数列前两个数都是1 '''
        r = 1
        return r  # 返回结果,并结束函数
    else:
        r = fib(n-1)+fib(n-2)  # 由数据的规律可知,第三个数的结果都是前两个数之和,所以进行递归叠加
        return r  # 返回结果,并结束函数


# print(fab(4))  # 3,调用函数并打印结果

'''
执行过程分析:
传入的 n=4, 执行: r = fib(n-1)+fib(n-2)  ---> fib(3)+fib(2)
fib(3)+fib(2) ---> fib(3) 执行后 ---> fib(2)+fib(1); fib(2)=1; fib(1)=1
所以: fib(3)+fib(2) = fib(2)+fib(1)+fib(2) = 1+1+1 =3

'''

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注