当前课程知识点：基于Linux的C++ > 第四讲 算法 > 4.6 递归算法（二） > LinuxCPP0406
这个例子叫汉诺塔问题
有了一个正确的递归思考方法以后
这个算法其实实现起来并不复杂
但是同学们要特别记住
如果使用一个非递归的算法来实现
那么如果你不知道它的实现技巧
硬生生去模拟栈框架调整过程的话
那么这个代码写起来
可以说是非常非常困难的
汉诺塔这个题什么意思呢
就是我们这里面有
分别命名为x和y、z的
这三个名字的塔座
然后还有一堆盘子
这些盘子大小都不一样
从小到大编号
1号、2号、……n号
然后我要搬这个盘子
x轴上一堆盘子移动到z上去
基本的规则就是：
一 这些盘子一次只能动一个
第二个 圆盘呢
x、y、z三个上面哪个都可以放
第三个 在任何时候
不能将大盘子放到小盘子的上面
这就这么三个规则
然后我们想怎么把这堆盘子
从x轴移动到z轴
那么我们要分析这个问题
该怎么去解决
我们现在要问自己俩问题
第一个 是不是存在一种最简单的情况
在这种情况下面问题很容易解决
第二个 是不是可以将原始问题
分解成性质相同
但是问题规模较小的问题
然后新问题的解答对原始问题的解答
具有重要的指导意义
这个就是我们要写递归算法的时候
同学们需要特别记住的两个地方
同学们回忆一下
怎么用数学归纳法来证明题
我是首先证明n等于1的时候成立
然后假设n=k成立的时候
证明n=k+1的时候成立
你怎么去找到从n=k成立的时候
到n=k+1成立的那个过程呢
先看看n=1的时候是什么样子
再看看n=2是什么样子
再看看n=3的时候是什么样子
看看能不能找到它的拼装规律嘛
这就是最重要一个地方
一个盘子我怎么搬呢 简单 直接挪
那我们想我怎么找n个盘子的规律呢
那我们就看两个盘子怎么办呢
我第一个盘子放到y轴上面临时放一放
然后第二盘子就能放到z轴了
就能挪过去了
然后把第一个盘子再从y轴上面
挪到z轴上放上去不就完了吗
这是两个盘子
那么三个盘子我怎么搬 就琢磨了
这其实应该把1号盘放到z轴
2号盘放到y轴
然后把1号盘再从z轴搬到y轴
这样的话两个盘就挪动到y轴上去了
按照这个模式
1号盘和2号盘合在一起作为一个整体
这个就是递归算法的实现策略
有了这个解决方案
那我们看汉诺塔演示动画
就完成了 四个盘子的完全的搬动
据此就可以写出汉诺塔的伪代码
一个MoveHanoi搬动这个汉诺塔
这里面带了4个参数
第一个参数是盘子有多少个 n
后面跟着3个参数就是三个轴的标志
我们定义枚举型HANOI
三个轴一个是from 一个是temp一个是to
一个是原始轴 一个是中转轴
一个是目标轴
我们写我们伪代码 if(n==1)
如果就一个盘子
那我就将这个盘子从from搬到to完事了
否则的话呢我就将它前面n-1个盘子
从from搬到temp临时放一放
这个时候的中转轴就是to
然后我就搬动第n号盘
从from搬动到to
在此之后将临时放一放的n-1个盘子
从temp搬到to
这个时候我们就以from为中转
搬过去就完了
这个就是汉诺塔这一道题的伪代码
你一看 是不是很简单
几行代码 非常短小
我们看看整个这个程序的具体实现
这个程序我们定义了一个枚举型HANOI
它的文字分别代表了
三个圆柱的代号：X、Y、Z
特别注意 因为要输出这个信息
模拟搬盘子的动作
在屏幕上全部打印出来
所以要有一个MovePlate
模拟几号盘从什么地方搬到什么地方
因为枚举型是不能够直接输出的
你直接输出的话
其实最终会转化成整数去输出
所以我们写一个函数ConvertHanoiToChar
把它转化成字符去输出
main函数的实现就是得到一个n值
然后移动汉诺塔
n个盘子 x、y、z三个轴
这是我们的程序代码
前面这两个都是我们原来都实现过的
就不解释了
然后ConvertHanoiToChar
使用一个switch语句
把这个枚举文字转换成字符
然后MovePlate就是单一一个盘子的搬动
我们把这个from转换成一个对应的字符
把to转换成一个对应的字符
然后我们就输出n号盘
从什么地方到什么地方
然后是MoveHanoi真实的代码
就是汉诺塔递归实现的真实代码 if(n==1)
把1号盘从from搬到to
如果不是最简单情形
那我就else MoveHanoi
n-1个盘子
从from以to为中转搬到temp
然后搬动第n号盘 从from搬到to
再然后把刚才搬到一边去的
n-1一个盘子
从temp以from为中转搬到to
这就是我们MoveHanoi递归函数的实现
确确实实看上去很简洁
程序代码就这么多
这就完成了全部程序
在实现这个递归函数的时候
同学们一定要记住
要养成最基本的递归信任
有的时候 初学者经常会觉得
这个递归函数能行吗
总是怀有疑虑 我要特别强调
递归它一定是能够正确工作的
养成最基本的递归信任
不用去怀疑递归工作基本原理
递归信任里面我们能够注意到六个问题
第一个
递归实现是不是检查了最简单情形
大量递归程序错误都是因为
最简单情形你没有检查到导致的
大部分情况下面
你的递归程序应该是if开头的
如果不是 你就要特别小心
这个程序十之八九就是错的
特别注意这一条
最简单情形你一定要有
第二个
这个最简单情形你是不是解决了
有的时候最简单情形我们可能没解决
当时给出问题解决方案不对
尤其同学们需要注意到
当我们解决最简单情形的时候
你不能调用递归
不是说它真地不能调用递归
你可以调用与它完全无关的一个递归
那个没问题
但是一定不能够再通过直接
或间接手段再去调用自己
最简单情形一定是不能这么干的
大部分递归程序
对于最简单的情形来讲
值都是简单直接设的过程
非常非常简单的语句
一般来讲都是这样
第三个 递归算法分解动作
是不是让问题更简单
这是非常重要的
问题规模不是越来越简单
而是问题规模越来越复杂了
这样搞下去 就没完没了了
你怎么能够得到结论呢
你是得不到结论的
第四个 问题简化过程
能不能够回归到最简单情形
还是遗漏一些情况
回不去就不成
这是非常重要的地方 特别要小心
也就是初始条件要写全了
第五个
子问题是不是和原始问题完全一致
你分解出来一个子问题
一定要和原来问题完全一致才行
如果它不完全一致 肯定就不成
相当于你偷换了概念
新的问题和原来的问题它就不一样了
它不是一个问题
就不能够用同样的方案去做
这个地方是一定要注意的
这是第五个
第六个 组装
使用递归实现 问题被你化简了
子问题的解也被求出来
结果组装给搞错了
那么这个问题的答案肯定也是不对的
就比如说刚才汉诺塔问题
它组装的过程是很明显的
要先把n-1个盘子
搬到临时轴那个地方放一放
然后把n号盘搬到你的目标轴Z
然后再把n-1的盘子
从临时中转轴搬到Z上
这是一个非常明确的过程
这就是一个组装 先一次递归调用
然后搬动最后一个大号牌
再来一次递归调用
如果你颠倒了一个次序
它就不对了
总体上来讲 在编写递归程序的时候
这六个地方要时刻保持警觉
确保它们都没有问题
你的递归函数就一定能够正确工作
这个就叫递归信任
-1.1 提纲
-1.2 程序设计的基本概念
-1.3 简单C/C++程序介绍
-1.4 程序设计的基本流程
-1.5 基本语法元素
-1.6 程序设计风格
-1.7 编程实践
-第一讲 C/C++基本语法元素--编程实践提交入口
-2.1 提纲
-2.2 结构化程序设计基础
-2.3 布尔数据
-2.4 分支结构
-2.5 break语句
-2.6 循环结构
-2.7 编程实践
-第二讲 程序控制结构--编程实践提交入口
-3.1 提纲
-3.2 函数声明、调用与定义
-3.3 函数调用栈框架
-3.4 编程实践
-第三讲 函数--编程实践提交入口
-4.1 提纲
-4.2 算法概念与特征
-4.3 算法描述
-4.4 算法设计与实现
-4.5 递归算法（一）
-4.6 递归算法（二）
-4.7 容错与计算复杂度
-4.8 编程实践
-第四讲 算法--编程实践提交入口
-5.1 提纲
-5.2 库与接口
-5.3 随机数库（一）
-5.4 随机数库（二）
-5.5 作用域与生存期
-5.6 典型软件开发流程（一）
-5.7 典型软件开发流程（二）
-5.8 编程实践
-第五讲 程序组织与开发方法--编程实践提交入口
-6.1 提纲
-6.2 字符
-6.3 数组（一）
-6.4 数组（二）
-6.5 结构体
-6.6 编程实践
-第六讲 复合数据类型--编程实践提交入口
-7.1 提纲
-7.2 指针基本概念
-7.3 指针与函数
-7.4 指针与复合数据类型（一）
-7.5 指针与复合数据类型（二）
-7.6 字符串
-7.7 动态存储管理（一）
-7.8 动态存储管理（二）
-7.9 引用
-7.10 编程实践
-第七讲 指针与引用--编程实践提交入口
-8.1 提纲
-8.2 数据抽象（一）
-8.3 数据抽象（二）
-8.4 链表（一）
-8.5 链表（二）
-8.6 链表（三）
-8.7 链表（四）
-8.8 函数指针（一）
-8.9 函数指针（二）
-8.10 抽象链表（一）
-8.11 抽象链表（二）
-8.12 编程实践
-第八讲 链表与程序抽象--编程实践提交入口
-9.1 提纲
-9.2 程序抽象与面向对象
-9.3 类类型
-9.4 对象（一）
-9.5 对象（二）
-9.6 类与对象的成员（一）
-9.7 类与对象的成员（二）
-9.8 类与对象的成员（三）
-9.9 继承（一）
-9.10 继承（二）
-9.11 继承（三）
-9.12 多态（一）
-9.13 多态（二）
-9.14 编程实践
-第九讲 类与对象--编程实践提交入口
-10.1 提纲
-10.2 四则运算符重载（一）
-10.3 四则运算符重载（二）
-10.4 关系与下标操作符重载
-10.5 赋值操作符重载（一）
-10.6 赋值操作符重载（二）
-10.7 赋值操作符重载（三）
-10.8 赋值操作符重载（四）
-10.9 赋值操作符重载（五）
-10.10 流操作符重载（一）
-10.11 流操作符重载（二）
-10.12 流操作符重载（三）
-10.13 操作符重载总结
-10.14 编程实践
-第十讲 操作符重载--编程实践提交入口
-11.1 提纲
-11.2 泛型编程概览
-11.3 异常处理机制（一）
-11.4 异常处理机制（二）
-11.5 运行期型式信息（一）
-11.6 运行期型式信息（二）
-11.7 模板与型式参数化
-11.8 题外话：术语翻译
-11.9 泛型编程实践（一）
-11.10 泛型编程实践（二）
-11.11 泛型编程实践（三）
-11.12 泛型编程实践（四）
-11.13 泛型编程实践（五）
-11.14 泛型编程实践（六）
-11.15 泛型编程实践（七）
-11.16 泛型编程实践（八）
-11.17 泛型编程实践（九）
-11.18 泛型编程实践（十）
-11.19 编程实践
-第十一讲 泛型编程--编程实践提交入口
-12.1 提纲
-12.2 程序执行环境（一）
-12.3 程序执行环境（二）
-12.4 程序执行环境（三）
-12.5 程序执行环境（四）
-12.6 输入输出（一）
-12.7 输入输出（二）
-12.8 文件系统
-12.9 设备
-12.10 库（一）
-12.11 库（二）
-12.12 makefile文件（一）
-12.13 makefile文件（二）
-12.14 makefile文件（三）
-12.15 编程实践
-第十二讲 Linux系统编程基础--编程实践提交入口
-13.01 提纲
-13.02 进程基本概念
-13.03 信号
-13.04 进程管理（一）
-13.05 进程管理（二）
-13.06 进程管理（三）
-13.07 进程间通信（一）
-13.08 进程间通信（二）
-13.09 进程间通信（三）
-13.10 进程间通信（四）
-13.11 进程池
-13.12 编程实践
-第十三讲 进程编程--编程实践提交入口
-14.1 提纲
-14.2 线程基本概念
-14.3 线程管理（一）
-14.4 线程管理（二）
-14.5 线程管理（三）
-14.6 线程管理（四）
-14.7 线程同步机制（一）
-14.8 线程同步机制（二）
-14.9 C++11线程库（一）
-14.10 C++11线程库（二）
-14.11 C++11线程库（三）
-14.12 C++11线程库（四）
-14.13 C++11线程库（五）
-14.14 编程实践
-第十四讲 线程编程--编程实践提交入口
-15.1 提纲
-15.2 Internet网络协议
-15.3 套接字（一）
-15.4 套接字（二）
-15.5 编程实践
-第十五讲 网络编程--编程实践提交入口
