python数据结构之递归

柳小葱 2021-10-26 03:29:04
Python 数据结构 递归 数据 结构

今天我们来学习python中最为重要的内容之递归,对以往内容感兴趣的同学可以查看下面:

最近开学呀、开题呀、然后懒呀、综上所述,很多天没写博客。但是天天都来上面看看,递归是在进行重复性工作中经常考到的问题,非常值得学习。

1. 递归的概念

递归是解决问题的一种方法,它将问题不断地分成更小的子问题,直到子问题可以用普通的方法解决。通常情况下,递归会使用一个不停调用自己的函数。尽管表面上看起来很普通,但是递归可以帮助我们写出非常优雅的解决方案。对于某些问题,如果不用递归,就很难解决。
上面的话很难理解,我们用一个例子来说明:我们需要求解一个数组的所有数值之和。

#用for循环的简单函数
def getsum(numlist):
a=0
for i in numlist:
a=i+a
return a

结果如下:
在这里插入图片描述
如果暂时没有 while 循环和 for 循环。应该如何计算结果呢? 这个时候就需要想到我们计算加法的时候,是接受2个参数的函数,根据这个思想,我们将求一列数之和重新定义成求数字对之和。
在这里插入图片描述
注:最内层的括号对(7 + 9)不用 循环或者其他特殊语法结构就能直接求解。
拟代码表示

#first(list)返回列表中的第一个元素,rest(list)则返回其余元素。用 Python 可以轻松地实现这个等式,
getsum(list)=first(list)+getsum(rest(list))

代码表示

#这是一个递归小案例,这个函数在函数内部自己调用了自listsum(numlist[1:])
def listsum(numlist):
if len(numlist)==1:#当数组的长度为1时,代表是数组是一个数了
return numlist[0]
else:
return numlist[0] + listsum(numlist[1:])#第一个数加上后面的数,这里自己调用了自己,是数组不断递归的条件

在这一段代码中,有两个重要的思想值得探讨。首先,第 2 行检查列表是否只包含一个元素。 这个检查非常重要,同时也是该函数的退出语句。对于长度为 1 的列表,其元素之和就是列表中的数。其次,listsum 函数在第 5 行调用了自己!这就是我们将 listsum 称为递归函数的原因——递归函数会调用自己。
演示一下相加过程
在这里插入图片描述

2. 递归三原则

递归算法有三个重要的原则:

  • 递归算法必须有停止条件
  • 递归算法必须改变其状态并向停止条件靠近
  • 递归算法必须递归地调用自己

让我们看看我们第一个案例是怎么实现这个部分的:

  • len(numlist)==1 用来判断停止条件
  • numlist[1:] 代表问题的数据以某种方式变得更小
  • return numlist[0] + listsum(numlist[1:]) 代表递归地调用自己

递归的逻辑并不是循环,而是将问题分解成更小、更容易解决的子问题。

2.1 实现任意进制的数据转换

下面展示一下将10进制的29转换为2进制数的方法,按照这个方法,可以将10进制转化为任意进制的数。
在这里插入图片描述
这里我们用递归来实现2~16进制数的转换

#n代表要转化的10进制数,base代表你要实现的多少进制的数
def toStr(n, base):
convertString = "0123456789ABCDEF"#取对应位置的字符
if n < base:#如果10进制数小于你所转换的进制数位数,则直接选择字符
return convertString[n]
else:#递归核心,n//base获取结果,然后进行递归
return toStr(n//base, base) + convertString[n%base]
版权声明
本文为[柳小葱]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_48077303/article/details/120842947

  1. django channels channel_layer.group_send 造成内存溢出
  2. Python布置了个感觉不大理解的题..
  3. Python a posé une question qui ne semblait pas très compréhensible.
  4. Python中yield返回生成器的详细方法
  5. Python函数中apply、map、applymap的区别
  6. Python字符串前加f、r、b、u的不同用法
  7. 5分钟教会你用Python采集CSDN的热榜
  8. 5分鐘教會你用Python采集CSDN的熱榜
  9. 5 minutes pour vous apprendre à utiliser Python pour collecter des listes chaudes de csdn
  10. Quick start of automation -- python (1) - [variables] - half an hour a day
  11. Python爬虫:给我一个链接,快手视频随便下载
  12. Python爬蟲:給我一個鏈接,快手視頻隨便下載
  13. 经验丰富程序员才知道的15种高级Python小技巧
  14. 經驗豐富程序員才知道的15種高級Python小技巧
  15. 15 conseils Python avancés que les programmeurs expérimentés connaissent
  16. Python crawler: Donnez - moi un lien pour télécharger des vidéos rapides
  17. Python爬虫:给我一个链接,快手视频随便下载
  18. [algorithm learning] sword finger offer 64. Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)
  19. 怎么系统的学习python,有没有一些比较完整的资料,基础知识+框架+项目实战此类pdf
  20. Python crawler: Donnez - moi un lien pour télécharger des vidéos rapides
  21. Python project management and construction, these four tools are enough!
  22. IDE的使用,pycharm引入Python库
  23. In the 120 series columns, you can learn the python beautiful oup4 module, 7000 word blog + climb the ninth workshop network
  24. Django运行xadmin 报错解析 ImportError: cannot import name 'DEFAULT_FORMATS' from 'import_export.admin'
  25. Python程序大学课程写程序
  26. Programme Python Programme d'études collégiales
  27. Python程序大學課程寫程序
  28. Django runxadmin Error resolution importerror: cannot Import name 'default Formats' from 'import _ Export.admin»
  29. Python 函数式编程,看这一篇足够了!
  30. 太棒了!11个好用到起飞的「Python字典」知识点!
  31. 一道Python题目,求解答!
  32. 一道Python題目,求解答!
  33. Un problème Python, s'il vous plaît!
  34. C'est génial! 11 points de connaissance du dictionnaire Python pour le décollage!
  35. Python Functional Programming, This is enough!
  36. 在python中beta分布的问题?
  37. 一个python习题,没有什么头绪,是关于进制的转换和绘制的,想了几天了,不仅仅是2,8,16这种常见的进制转换
  38. Un exercice Python, qui n'a pas beaucoup d'idées, est sur la conversion et le rendu décimaux et a pensé pendant quelques jours, pas seulement 2, 8, 16 cette conversion décimale commune
  39. Un problème avec la distribution bêta en python?
  40. python实现简单的读取excel 内容,报错
  41. L'implémentation Python lit simplement le contenu d'Excel et signale les erreurs
  42. 用Python定义一个函数,接收n个数字,求这些参数数字的和
  43. Définissez une fonction en python, recevez n nombres et additionnez ces nombres de paramètres
  44. 上电Python写文件后,再断电后导致文件内容丢失
  45. 上電Python寫文件後,再斷電後導致文件內容丟失
  46. Une fois que Python est allumé pour écrire des fichiers, le contenu des fichiers est perdu après une panne de courant
  47. python套接字编程报错:ConnectionResetError: [WinError 10054] 远程主机强迫关闭了一个现有的连接。
  48. 【Python从入门到精通】(二)怎么运行Python呢?有哪些好的开发工具(PyCharm)
  49. 【Python从入门到精通】(二)怎么运行Python呢?有哪些好的开发工具(PyCharm)
  50. Python语法1
  51. 2018年度最受推荐的10本Python书籍(初学者必看)
  52. Les 10 livres Python les plus recommandés en 2018 (obligatoire pour les débutants)
  53. Syntaxe Python 1
  54. Python语法1
  55. 在python 运行celery时候 AttributeError: 'NoneType' object has no attribute 'Redis'错误
  56. Attributeerror: 'nonetype' Object has no attribute 'redis' Error when Celery is running in Python
  57. Syntaxe Python 1
  58. Python celery is a plug-in that focuses on distributed asynchronous task processing and task scheduling!
  59. Python celery is a plug-in that focuses on distributed asynchronous task processing and task scheduling!
  60. 在python,使用scrapy爬虫框架