数据结构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

智能推荐

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/

推荐文章

热门文章

相关标签