我们都听过猜数字游戏吧 sorry 是汉诺塔游戏 我们先来看一个简化版的汉诺塔游戏 把4个盘子始终保持 大盘子在下面 小盘子在上面的状态 由第一根针借助于第二根针 移到第三根针上 可以看到 可以让第二个人将较小的3个盘子 按照要求 借助第三根针移到第二根针上 自己移动最大的盘子 到第三根针上 再让第二个人将较小的3个盘子 由第二根针借助第一根针 移到第三根针上 第二个人可以找第三个人帮助他 移动较小的2个盘子 自己则移动第3个 最大(三个中)的盘子 依次类推就可以完成任务 我们可以感觉到 这个问题没有明显的循环解决方案 但是似乎可以感觉到 有另外一种独特的方式来解决 这是什么方式呢 就是递归 递归是最能表现计算思维的算法之一 我们用生成 第N个斐波拉契数列的例子 来说明一下递归的思想 先来看求第N个斐波拉契数列的 循环实现方式 我们知道斐波拉契数列 它的形式是这样的 第一个元素是0 第二个是1 后面的每一项是前两项之和 所以它是这样的一个数列 在循环里面很简单 初值定好a和b 然后不断地进行更新 把b不断地赋给a a+b赋给b 最后输出a的值 而我们用递归的思想怎么实现呢 我们知道当值是0或1的时候 返回的就是它的本身 往后看 这一项 比如说它是f(n) 是不是是f(n-2)和f(n-1)之和 是不是应该是这样子的 递归程序写出来是这样子 n等于0或1的时候return n else return f(n-1)+f(n-2) 我们看到递归的代码是不是更加简洁 更加好理解 符合我们的自然逻辑 在写递归程序的时候 要特别注意的有两点 第一个要有递归停止的条件 也就是要有递归的出口 在这里我们看到 在n是0或1的时候我们返回n 这就是它的出口 另外反复调用的是 原始内容的副本 这个副本要比原来要简单 不能在这里写f(n)加上f(n) 这样的话它就没法回归 我们简单来看一下 这个程序的执行的过程 例如要求第5个元素 也就是计算f(4) f(4) return f(3)+f(2) 而f(3)是return f(2)+f(1) f(2)是return f(1)+f(0) 其实在这一支的话已经有结果了 因为f(1)可以return 1 f(0)是return 0 其他的话同样类似 到了return 1或者0 这样的一个位置 其实已经是 回归过程的某一些部分已经结束了 可以一层一层往上返回 这边其实是一个递推的过程 等到每一个值都往上返回以后 最后我们能够计算出f(4)的值 这就是一个递归的过程 我来问大家一个问题 大家思考一下 (同一程序)你觉得是循环的执行效率高 还是递归的执行效率高 我估计很多同学会说是递归 因为递归看上去很简洁 其实递归它的执行效率并不高 系统的资源消耗比循环要大 因为它是一层一层地往里面调用 并且结束以后一层一层地返回 所以它的执行效率并不高 那为什么还用递归呢 因为有一些问题 我们找不到非常明显的循环的方案 但是有非常明显的递归的方案 比如说著名的汉诺塔问题 汉诺塔来源于印度的一个神话 因为这个问题本身比较复杂 所以我就直接让大家来看程序 我们来理解一下 假设有四个盘子 程序的结果要输出整个的移动过程 函数有四个参数 前三个参数 分别代表某一根针上最上面的那个盘子 比如说如果是这样的一个输出 就代表 从“a”这根针上面拿一个盘子 拿哪个盘子呢 最上面那个盘子移到“c”上面 我们来看程序 如果是大于一个盘子的时候 我们是不是可以这样来考虑 所有“a”针上的盘子 我们可以把其中上面的n-1个 借由“c”先移到“b”上面 比如说假设这是它的n-1个盘子 那这是最下面的一个大的盘子 我们可以借助“c”移到“b”上面 另外一个盘子 是不是可以直接搬过来 就是直接从“a”到“c” 所以这里面我们看到 函数可以这样来写 “a”借助“c”移到“b”上面 多少个呢 是n-1个盘子 接下来这步是“a”到“c” 也就是拿一个盘子 再下面怎么做 是不是应该把这n-1个盘子 从“b”上面借助“a”移到“c”上面 所以我们看借助“a”移到“c”上面 这个问题的出口在哪里呢 到n是等于1的时候 也就是说只有1个盘子的时候 我们是不是可以这样子 直接从“a”上面移到“c”上面 所以如果是4个盘子的话 最后移动的过程就是这样的过程 我把3个盘子的移动过程 留给大家来做练习 同时我们可以思考一下 如果n个盘子的话需要多少步 来看两个典型的递归函数 这两个函数一个是用return返回结果 另一个是任务型的直接输出结果 先来看第一个函数f1 假设我们传入的实参分别是3和5 那么if条件不成立所以执行else部分 返回3+f(3,4) f(3,4)是挂着的还没有结果 我们接着计算f(3,4) 同样要选择else分支 f(3,4)等于3+f(3,3) 接着f(3,3)等于3+f(3,2), 依次计算 直到什么时候会返回呢 直到b等于1的时候也就是f(3,1)时返回3 回归过程结束 再接着完成递推 前面没有获得结果的函数 逐个获得前一轮递归的返回值 逐级返回最后获得结果 就是3+3+3+3+3等于15 我想大家肯定看出来了 这个函数的功能就是 模拟了加法实现乘法的过程 对于这类需要返回的函数要特别强调一下 这个return是必须要写的 因为如果不写的话 除了b等于1时f(a, 2) 因为b等于1时有返回能获得值 其他的函数如f(a, 3) 因为缺少return拿不到f(a, 2)的值 所以这个return不能少 再来看第二个函数f2 这个函数中不包含return语句 直接输出结果 我们来理解一下这个函数 假设实参n是8 if条件满足 所以执行f2(8//2)即f(4) 这个函数暂时挂起来没有结果 接下来这条print()语句输出n%2 等于0 问题的关键来了 这个0是马上就输出吗 想一想 想到了吧 应该不是 因为这条print()语句 是在f2(n//2)这条语句之后执行的 所以f2(n//2)语句 没有执行完输出0就不会执行 我们是不是就可以理解如果n是8时 0就应该位于输出结果的最后一个 理解好了这个地方我相信其他部分的理解不难 这个函数的功能 是将十进制数转换成二进制形式并输出 来运行程序并看一下结果 f1(3,5)结果是15 f2(8)结果是1000