当前课程知识点：基于Linux的C++ > 第四讲 算法 > 4.5 递归算法（一） > LinuxCPP0405
接下来一小节就是我们要讨论
一个非常重要的一种算法
我们称它为递归算法
我们知道 在数学上求一个数列的时候
经常会使用一种所谓的通项公式
可是还有的时候
我们给的不是通项公式 叫递推公式
数学上是非常常见的
比如阶乘函数 1!是1
然后n!就是n乘上(n-1)!
这就是一个递推的公式
n的阶乘是怎么算呢
是n-1的阶乘算出来以后
然后乘上n装配上来的
n-1的阶乘怎么算呢 同样的原则算
这个就叫递推公式
这在数学上非常非常常见
计算机编程的时候就必须考虑这一点
怎么去实现它
还有第二种你看斐波那契数列
斐波那契数列f(1)、f(2)等于1
然后f(n)就等于f(n-1)加上f(n-2)
注意到所有的数学上的
递推公式都是分段函数
总有一个初始表达式
那么计算过程呢
你就得知道 问题规模逐步简化
如果设f(n)括号里面的那个n值
是问题规模的话
f(n-1) 那个n-1就是它的问题规模
n-1比n小吧
那就叫问题规模逐渐简化
递推都是这样工作的
所以写递归程序的时候
同学们要特别记住的
就是我们这里面实际上包括两部分
第一个我要完成一个递推
把f(n-1)分解成f(n-2)、f(n-3)
n!分解成(n-1)!
(n-1)!分解成(n-2)!
必须按照这个过程逐步分解问题
让这个问题越来越简单
然后第二步我要回归
我用1!装配出2!来
用2!装配出3!
这就是递推加回归
合在一起我们就称它为递归
那么我们怎么实现像这样的阶乘函数
和递归函数呢 先看阶乘函数
现在给出两种实现策略
一种叫循环策略
一种叫做递归实现的策略
先看循环策略
那么很简单 我定义一个i
定义了一个结果result
把result初始化成1
i初始值初始成0 然后while
++i之后 i<=n
把这个i值乘到result上去
把1乘上去 2乘上去 一直乘到n
全乘上去以后结果就是阶乘
函数就结束了
你看我的代码 四行 很短吧
你会觉得这个代码很容易理解
那么如果我们用递归怎么来实现呢
在这里面我也定义一个result
我就按照递推那个式子
阶乘这个定义来
如果n是1
result就赋值为1
else result就赋值为n乘上(n-1)!
return result结果就行了
我(n-1)!怎么来的
这就涉及到递归函数
最重要的一个地方了 你注意看
我这个函数名字叫GetFactorial
求这个阶乘 传的参数是n
那么我怎么求(n-1)!呢 就调用它呗
这个函数不就是算阶乘了吗
一个函数通过直接或间接的手段
调用自身的动作就叫递归
这样的函数就叫递归函数
我们看第二个
刚才那个例子看得不明显
不管使用递归实现还是循环实现
它的代码其实都蛮短的
所以你感觉不到它们之间的差异
那我们看斐波那契数列
这个其实就特别明显
如果使用递归实现的话
其实策略跟刚才非常非常相似
就是这么写的 if(n==2||n==1)
return 1
else return GetFibonacci(n-1) + GetFibonacci(n-2)
这里面会产生两次递归 没关系啊
按照它的定义就应该这么来
那我们这么写就行了
很典型吧 四行代码 解决了
回到循环实现 如果if(n==2||n==1)
结果是很明确的return 1
接下来我们要做f3
有了f3我才能装配出f4
所以要一个循环来装配
我要把1给f2 然后把1给f1
然后写一个for循环 开始装配
f3赋值为f1加f2
然后把f2作为新的f1
刚刚算出来f3作为新的f2去算新的f3
那其实就是变成f4了
我们就不断往下循环 依次迭代
去找它的fn
按照这样的方式去实现的话
这个代码量
明显比我们递归实现代码量要大很多
这是非常重要的一个地方
就是对于同样一个问题来求解的话
使用递归实现往往要比
使用循环实现的代码量要短很多
我们可以对循环和递归
做一些简单的比较
首先呢循环是用显示的循环结构
来执行我们的代码段
而递归是使用函数调用
来重复执行代码段 这是第一点
第二点 循环是在
满足终止条件的时候终止执行
递归 要到退化到最简单的情形的时候
它才能够终止执行
第三个 循环的重复
是在当前迭代执行完毕以后
递归的重复在发现到它对同名的函数
也就是它自身的一次函数调用的时候
第四个 循环也好 递归也好
都可能在程序中藏着程序错误
所以你检查的时候都是需要特别小心的
最后一个 同学们要特别记得
理论上任何一个递归程序代码
都可以使用循环来重新实现
这都没有问题
但是我要跟同学们特别强调
一 大部分程序递归算法
非常非常的短小精悍 简单 代码量短
第二 有一些函数
当你使用循环来实现的时候
当你没有发现技巧的时候
用循环来实现其实是相当相当困难的
但使用递归
一旦你养成了正确的递归思考方法以后
递归的实现策略
其实是非常简单和直接的
我们来看一个例子
递归函数的调用栈框架
当它调用的时候会发生什么事情呢
我们就用刚才那个
阶乘函数的例子来展示
这个里面定义了一些函数原型
写在了main函数前面
接下来在main函数里面得到这个整数
然后就调用GetFactorial去算它的阶乘
具体的实现就是刚才那一段代码
这个我就不解释了
关键的问题是
我们关注函数栈框架的调整
一个main函数里面 有n 又有result
我们假设n的值是3
3!能算吗
调用GetFactorial这个函数去算3!
发现3!没法直接算
它必须用3乘上2!去装配
所以它会产生一次递归调用
当它产生这个递归调用的时候
第一次调用GetFactorial这个函数
并没有结束
它就会调用第二次GetFactorial这个函数
n的值就会传进去2
这就是第二次函数调用
你会看到第二次调用
GetFactorial函数的栈框架
覆盖了第一次调用的栈框架
递归调用发生的时候
就是按照这个模式
递归调用栈框架不断覆盖上去
然后不断再重新消失这个过程
这就是我们函数调用栈框架
2!能够直接算吗 还不能
我们必须继续调用GetFactorial
第三次调用GetFactorial
n传进去1
我现在能够简单直接得到阶乘值吗
是的 1!为1 这是我们的定义
它的初始表达式里面
就包含了这样一个定义
那么 我们就直接写result赋值为1
正常情况下来讲
这个函数就可以直接return了
GetFactorial这个函数栈框架就会消失
就是第三次调用的
这个栈框架就会消失
然后把1的结果
传给第二次调用的GetFactorial
然后一乘2 结果就出来了
结果出来它就会消失
然后第一次调用的GetFactorial
这个函数栈框架就出来了
乘上3 结果是6
然后它的结果也出来了
它的栈框架也消失
然后main就得到结果6
3!为6
这就是递归调用的时候函数栈框架
从刚才那个演示里面
你就看得非常清楚
对于一个递归函数GetFactorial
它是一次一次调用
最先调用的那一次最后消失
所以这就叫栈嘛
满足先进后出规则的一种特殊结构
我们的函数调用就是这么工作的
我们计算机的原理就是这么定的
所以我们整个递归调用
就必须按照这样方式进行工作
这是我们函数调用栈框架
-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 编程实践
-第十五讲 网络编程--编程实践提交入口
