WEB开发者-分享WEB开发知识,让开发变得更简单!

一篇文章带你了解Python递归函数

一篇文章带你了解Python递归函数

一、什么是递归函数?

在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。

二、函数的递归调用原理

实际上递归函数是在栈内存上递归执行的,每次递归执行一次就会耗费一些栈内存。

栈内存的大小是限制递归深度的重要因素

三、案例分析

1.求阶乘

计算阶乘n! = 1 x 2 x 3 x … x n,

可以用函数fact(n)表示。

  1. fact(n) = n! = 1 x 2 x 3 x … x (n-1) x n = (n-1)! x n = fact(n-1) x n 

fact(n)可以表示为n x fact(n-1),只有n=1时需要特殊处理。

于是,fact(n)用递归的方式写出来就是:

  1. def fact(n): 
  2.     if n == 1: 
  3.         return 1 
  4.     return n * fact(n - 1) 

如果计算fact(6),可以根据函数定义看到计算过程如下:

  1. def fac(n): 
  2.     if n==1: 
  3.         return 1 
  4.     else
  5.         res=n*fac(n-1) 
  6.         return  res 
  7.  
  8. print(fac(6)) 

运行结果:

一篇文章带你了解Python递归函数

2.斐波拉契级数

有这样一个数列:1,1,2,3,5,8,13,21,34…。其第一元素和第二个元素等于 1,其他元素等于其前面两个元素的和。

例:

  1. def fab(n):  # 定义斐波拉契级数 
  2.     if n in [1, 2]:  # 如果n=1或者2 
  3.       return 1 
  4.     return fab(n - 1) + fab(n - 2)  # n>2 
  5.  
  6.  
  7. print(fab(1))  # 斐波拉契级数的第一个元素 
  8.  
  9. print(fab(2))  # 斐波拉契级数的第二个元素 
  10.  
  11. print(fab(8))  # 斐波拉契级数的第8个元素 
  12. print(fab(13))  # 斐波拉契级数的第9个元素    

运行结果:

一篇文章带你了解Python递归函数

3.递归函数的优点

定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。

递归需要注意递归的深度。由于递归会产生多次函数调用,而函数调用会消耗代码的栈空间,如果递归的深度太大,会导致栈溢出。以上面的阶乘为例,如果计算 100000 的阶乘,在一般机器上都会出现栈溢出的问题。

  1. print(fac(10000)) 

如下所示:

一篇文章带你了解Python递归函数

四、总结

本文基于Python基础。Python标准的解释器没有针对尾递归做优化,任何递归函数都存在栈溢出。介绍了在使用递归函数的优缺点,优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。

在实际案例中,针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的,没有循环语句的编程语言只能通过尾递归实现循环,进行详细的讲解。

使用Python语言,希望能够帮助你更好的学习。

一篇文章带你了解Python递归函数

【编辑推荐】

  1. 跟妹妹聊到 Java 16 新特征,真香!
  2. IT项目过多,管理太难?NO!因为你还没学会这七招
  3. 学了五年Python,这些网站让我相见恨晚,快来一起见识一下
  4. Java都到16了,为什么都还在用8,是越做越烂了么?
  5. 实在太神奇!Windows10这些黑科技小功能你都用过吗

本文链接:https://www.webkfz.com/zixun/mxh3.html

版权声明:站内所有文章皆来自网络转载,只供分享作用,不代表本站的观点!

发表评论 共有 0 条评论)

联系客服
网站客服 业务合作 QQ
1244305267
公众号
公众号
公众号
返回顶部