4.1递归的概念与应用（Python进阶-数据结构与算法）课件

什么是递归 数据结构与算法（Python版） ❖ 递归是一种解决问题的方法 ， 其精髓在于 将问题分解为规模更小的相同问题， 持续分解，直到问题规模小到可以用非常简单直 接的方式来解决。 递归的问题分解方式非常独特，其算法方面的明 显特征就是：在算法流程中调用自身。 ❖ 递归为我们提供了一种对复杂问题的优雅 解决方案 ， 精妙的递归算法常会出奇简单 , 令人赞叹。 什么是递归Recursion？ 数据结构与算法（Python版） 0 ❖ 问题：给定一个列表 ， 返回所有数的和 列表中数的个数不定，需要一个循环和一个累加 变量来迭代求和 ❖ 程序很简单 ， 但假如没有循环语句？ 既不能用for，也不能用while 还能对不确定长度的列表求和么？ 数据结构与算法（Python版） 初识递归：数列求和 0 ❖ 我们认识到求和实际上最终是由一次次的 加法实现的 ， 而加法恰有2个操作数 ， 这 个是确定的。 ❖ 看看怎么想办法 ， 将问题规模较大的列表 求和 ， 分解为规模较小而且固定的2个数 求和（加法） ？ 同样是求和问题，但规模发生了变化，符合递归 解决问题的特征！ 数据结构与算法（Python版） 初识递归：数列求和 0 ❖ 换个方式来表达数列求和：全括号表达式 (1+(3+(5+(7+9)))) ❖ 上面这个式子 ， 最内层的括号(7+9) ， 这 是无需循环即可计算的 ， 实际上整个求和 的过程是这样： 数据结构与算法（Python版） 初识递归：数列求和 0 ❖ 观察上述过程中所包含的重复模式 ， 可以 把求和问题归纳成这样： 数列的和=“首个数 ”+“余下数列 ”的和 ❖ 如果数列包含的数少到只有1个的话 ， 它 的和就是这个数了 这是规模小到可以做最简单的处理 listsum(numList)=first(numList)+listsum(vest(numList)) 问题 分解 相同问题，规模更小 数据结构与算法（Python版） 初识递归：数列求和 0 ❖ 上面程序的要点： 1，问题分解为更小规模的相同问题，并表现为 “调用自身 ” 2，对“最小规模 ”问题的解决：简单直接 数据结构与算法（Python版） 最小规模 ❖ 上面的递归算法变成程序 初识递归：数列求和 0 调用自身 减小规模 数据结构与算法（Python版） ❖ 递归函数调用和返回过程的链条 递归程序如何被执行？ 0 ❖ 为了向阿西莫夫的“机器人三定律 ”致敬 , 递归算法也总结出“三定律” 1，递归算法必须有一个基本结束条件（最小规 模问题的直接解决） 2，递归算法必须能改变状态向基本结束条件演 进（减小问题规模） 3，递归算法必须调用自身（解决减小了规模的 相同问题） 数据结构与算法（Python版） 递归“三定律” 0 ❖ 数列求和问题首先具备了基本结束条件 ： 当列表长度为1的时候 ， 直接输出所包含 的唯一数 ❖ 数列求和处理的数据对象是一个列表 ， 而 基本结束条件是长度为1的列表 ， 那递归 算法就要改变列表并向长度为1的状态演 进 我们看到其具体做法是将列表长度减少1。 ❖ 调用自身是递归算法中最难理解的部分 ， 实际上我们理解为“ 问题分解成了规模更 小的相同问题”就可以了 在数列求和算法中就是“更短数列的求和问题 ” 递归“三定律”：数列求和问题 数据结构与算法（Python版） 0 ❖ 这个在数据结构栈里讨论过的算法 ， 又回 来了！ 递归和栈， 一定有关联 ❖ 如果上次你被“入栈 ”“ 出栈 ”搞得挺晕 乎的话 ， 这次递归算法一定会让你感到清 新 而且这次我们要解决从二进制到十六进制的任意 进制转换 数据结构与算法（Python版） 整数转换为任意进制 0 ❖ 我们用最熟悉的十进制分析下这个问题 十进制有十个不同符号： convString = "0123456789" 比十小的整数，转换成十进制， 直接查表就可以 了： convString[n] 想办法把比十大的整数，拆成一系列比十小的整 数，逐个查表 比如七百六十九，拆成七、六、九，查表得到 769就可以了 数据结构与算法（Python版） 整数转换为任意进制 0 ❖ 所以 ， 在递归三定律里 ， 我们找到了“基 本结束条件” ， 就是小于十的整数 拆解整数的过程就是向“基本结束条件 ”演进的 过程 ❖ 我们用整数除 ， 和求余数两个计算来将整 数一步步拆开 除以“进制基base”（// base） 对“进制基 ”求余数（% base） 数据结构与算法（Python版） 整数转换为任意进制 0 0 ❖ 问题就分解为： 余数总小于“进制基base”，是“基本结束条件 ”,可直接进行