数据结构17：什么是递归_xddwz的博客-程序员宝宝_递归是什么意思

技术标签： 算法  python  数据结构  

 

目录

 

一、什么是递归（Recursion）？

二、初始递归：数列求和问题

1、问题分析

2、代码实现

3、代码分析

4、递归程序如何被执行

三、递归三定律

一、什么是递归（Recursion）？

递归是一种解决问题的方法，其主要思想在于：

  • 将问题分为规模更小的相同问题
  • 持续分解，直到问题规模小到可以用非常简单直接的方式来解决

递归问题的分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。递归为我们提供了一种对复杂问题的优雅解决方案，精妙的递归算法常会出奇简单，令人赞叹。

二、初始递归：数列求和问题

问题：给定一个列表，返回所有数的和。列表中数的个数不定，大家可能很容易的想到用一个循环和一个累加变量迭代的实现，如下代码：

def listSum(numlist):
    Sum = 0
    for num in numlist:
        Sum = Sum + num
    return Sum

这样的程序很简单，但是假如没有循环语句呢？既不用循环for，也不用while，还能对不确定长度的列表求和吗？

1、问题分析

我们直到，列表求和实际上是由一次次的加法实现的，而加法只有两个操作数，这是确定的。

那是否可以想办法，将问题规模较大的列表求和，分解为规模较小而且固定的两个数求和呢？这样的话，同样是求和问题，但是规模发生了变化，符合递归解决问题的特征。

首先，我们换个方式来表示列表求和：全括号表达式：(1 + (3 + (5 + (7 + 9))))

上面的式子中，最内层的括号(7 + 9)，这是不需要循环的，可以直接计算，实际上整个求和的过程是这样的：

观察上面的过程所包含的重复模式，可以把求和问题归纳为：

数列的和 = “首个数” + “余下数列”的和

如果数列包含的数烧到只有一个的话，他就是这个数列的和了。

2、代码实现

def listSum(numlist):
    if len((numlist)) == 1:
        return numlist[0]
    else:
        return numlist[0] + listSum(numlist[1:])

3、代码分析

上面的程序中：

  • 将问题分解为更小规模的相同问题，并表现为调用自身。
  • 对最下规模问题的解决：简单直接

4、递归程序如何被执行

递归函数调用和返回过程的链条：方向相反

三、递归三定律

  • 递归算法必须有一个基本技术条件：最小规模问题的直接解决
  • 递归算法必须能改变状态项基本结束条件演进：减小问题规模
  • 递归算法必须调用自身：解决减小了规模的相同问题

关于数列求和问题：

数列求和问题首先具备了基本结束条件，当列表长度为1的时候，直接输出所包含的唯一数。

数列求和问题中，递归算法就是改变列表的长度，并向长度为1的状态演进。

调用自身是递归算法中最难理解的部分，实际上可以理解为：问题分解为了规模更小的相同问题。

 

 
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/xddwz/article/details/108435207

智能推荐

嵌入式linux驱动学习之应用层数据如何和驱动层数据进行交互_应用层和驱动层通过什么进行交互_Jason～F的博客-程序员宝宝

linux驱动学习之应用层数据和内核层数据的互通

layui.js:238 请求方式/路径 .....undefinedcss/modules/layer/default/layer..css?v=3.1.1 net::ERR_ABORTED 404_青春a的博客-程序员宝宝_layer.css 3.1.1 下载

我的问题是因为 引入了两个js一个layer.js一个layui.js导致layer的东西不能正常使用删掉layer.js即可

2013腾讯实习生笔试错误题目集锦_overstack的博客-程序员宝宝_实习笔试错几个能过

这篇博客目的只是记录今天笔试本人错误的题目，供后面复习用.并没有泄露试题的意思........1. 32位的机子，下面的说法哪些是正确的？ signed char a = 0xe0; unsigned int b = a; unsigned char c = a;A. a>0 && c>0B. a==cC. b的十六进制的表示是：0xffffffe0D

vscode如何找letax模板_LaTeX技巧932：如何配置Visual Studio Code作为LaTeX编辑器[新版更新]..._weixin_39693438的博客-程序员宝宝

1. 为什么用 Visual Studio CodeVisual Studio Code(以下简称 VS Code) 是微软推出的一个编辑器，它的优点你可以百度一下，这里不赘述。对我来说，它最有吸引力的当属在 Windows 系统，它对于中英文字体的渲染。如果你原来用过其他编辑器，你就知道在普通屏幕上，中英文的显示效果简直是灾难。我原来因为编辑器的中文显示(当然还有 Terminal 的吸引力)一...

大话编程之ASP.Net和ASP区别_weixin_30716725的博客-程序员宝宝

ASP.Net和ASP的最大区别在于编程思维的转换，而不仅仅在于功能的增强。ASP使用VBS/JS这样的脚本语言混合html来编程，而那些脚本语言属于弱类型、面向结构的编程语言，而非面向对象，这就明显产生以下几个问题：1、代码逻辑混乱，难于管理：由于ASP是脚本语言混合html编程，所以你很难看清代码的逻辑关系，并且随着程序的复杂性增加，使得代码的管理十分困难，甚至超出一个程序员所能达到的管理能...

程序员新手速成之六脉神剑_别君且坐思过处lh的博客-程序员宝宝

程序员新手速成之六脉神剑引子· 武侠梦大家好，我是一名程序员，小时候呢，非常喜欢金庸武侠。记得吴启华版《倚天屠龙记》中，少年张无忌无意进入光明顶秘密石室，机缘巧合之下，习得已故教主阳顶天留下的《乾坤大挪移》心法。由于自身《九阳神功》加持，天下武学，融会贯通，俯首可得，张无忌因此在最短的时间内，学到了第七层。每次看到这里，总是激动不已，要是我有这么好的机缘该多好啊！可惜，现实是残酷的，武侠梦做的再好，还是无法避免码农的命运！作为入坑多年的Java程序员...

随便推点

【BZOJ 1178】【APIO 2009】CONVENTION会议中心_as2886089的博客-程序员宝宝

http://www.lydsy.com/JudgeOnline/problem.php?id=1178这道题想了好久没想明白，倍增数组通过看题解很快就明白了，但是一小段区间内应有的最多线段数一直不知道怎么记录。后来聪哥提醒我才明白，直接getans(l,r)不就完了吗_(:з」∠)_根本不用记录啊QwQ我用splay维护线段的位置顺序，查找前驱后继等等。上午因为懒得写插入线...

PageHelper实现_飞乐鸟的博客-程序员宝宝_pagehelper实现

添加依赖：<!-- pagehelper分页模块 --><dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper</artifactId> <version>5.1.2</v

fastjson后某些字符有转义符_树上的疯子^的博客-程序员宝宝_fastjson 转义字符

尤其是特殊字段如果有转意义字符就有问题使用 StringEscapeUtils.unescapeJavaScript(jsDataStr) 解决!!!

mysql5.5 my.ini优化,mysql优化 my.ini高手设置_一瓶辣酱的博客-程序员宝宝

据说这是高手优化的mysql,供大家参考,其中连接数 max_connections=1500可以根据服务器的性能更改.pc136.com 版权所有#set-variable = connect_timeout=5#set-variable = wait_timeout=5 pc136.com 版权所有建议启用,负担重的服务器可以适当减少持续连接时间PC易上路[mysq...

linux7安装tools提示目录不在,关于Centos7安装vmtools时，存在kernalheaderd仍然找不到路径的问题..._weixin_39664585的博客-程序员宝宝

今天在安装vmtools出现的找不到kernel headers的问题，主要原因是版本不匹配！在第一次安装时，提示gcc路径找不到,安装gcc以后又出现kerneal headers路径找不到。但是检查/usr/src/kernel路径时发现kernel文件时存在的。于是运行：rpm -qa|grep kernelkernel-tools-libs-3.10.0-957.el7.x86_64ker...

QT 资料档案库_小松萘的博客-程序员宝宝_qt资料档案库

教程1教程2http://mirrors.ustc.edu.cn/qtproject/online/qtsdkrepository/windows_x86/root/qt/

推荐文章

热门文章

相关标签