Python学习系列之递归函数(二十一)

递归函数

一、什么是递归函数

如果在一个函数的函数体内调用了该函数本身,这个函数就称为递归函数

 

二、递归的组成部分

  递归调用与递归终止条件

 

三、递归的调用过程

  1.每递归调用一次函数,都会在栈内存分配一个栈帧

  2.每执行完一次函数,都会释放相应的空间

 

四、递归的优缺点

  缺点:占用内存多,效率低下

  优点:思路和代码简单

案例:计算6的阶乘

6的阶乘示意图:

Python学习系列之递归函数(二十一)

 

 

 代码:

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

print(fac(6))

  执行结果:

Python学习系列之递归函数(二十一)

 

 

 调用debug模式,可以查看函数执行过程,可以看到,先去计算fac(n-1),不会执行到return res这一行,直到n=2,执行fac(2-1)即n=1,则会执行return 1,然后向上逐层计算n*fac(n-1),将结果保存到res,一层一层向上返回计算结果,最后返回res的结果720

Python学习系列之递归函数(二十一)

 

 

一直点击debug模式的向下箭头,能看到各层的计算结果

 Python学习系列之递归函数(二十一)

 

 

 五、裴波那契数列

1. 什么是裴波那契数列

1 1 2 3 5 8 13.... 即第1个位置上是1,第2个位置上是1,第三项是前两项之和即2,第四项是3=1+2,以此类推

2. 代码示例

'''裴波那契数列'''
def fib(n):
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

#求裴波那契数列第6位上的数字
print(fib(6))

  执行结果:

Python学习系列之递归函数(二十一)

 

 

 如果要一次输出裴波那契数列的前面6位数字呢?只需要使用一个for循环输入1-6的值即可,代码如下:

def fib(n):
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

#求裴波那契数列前6位的数字
for i in range(1,7):
    print(fib(i))

  执行结果:

Python学习系列之递归函数(二十一)

 

 --------------------------------------------------

函数总结

1. 函数的定义与调用

  函数定义使用def定义

  函数定义的形参有:*定义个数可变的位置形参,**定义个数可变的关键字形参,定义默认值参数

  函数调用的实参:位置实参,关键字实参

  函数可以有多返回值

2.变量的作用域

  变量由全局变量和局部变量,通过用global声明局部变量,可是局部变量变成全局变量

3.递归函数

  递归函数就是函数本身调用本身

  递归的组成部分:调用条件和终止条件

 

上一篇:7-15 计算圆周率 (15 分)


下一篇:SP3734 PERIODNI - Periodni 笛卡尔树 DP