当前课程知识点:C++语言程序设计基础 > 第3章 函数 > 嵌套与递归 > 函数的递归调用(例3-8)
函数的递归调用
l 函数直接或间接地调用自身,称为递归调用。
l 公式1:n!=n×(n-1)×(n-2)×(n-3)×...×2×1.
l 公式2:
l 递推:
l 回归:
源代码:#include <iostream>
using namespace std;
unsigned fac(int n){
unsigned f;
if (n == 0)
f = 1;
else
f = fac(n - 1) * n;
return f;
}
int main() {
unsigned n;
cout << "Enter a positive integer:";
cin >> n;
unsigned y = fac(n);
cout << n << "! = " << y << endl;
return 0;
}
运行结果:
Enter a positive integer:8
8! = 40320
大家好
欢迎继续学习C++语言程序设计
这一节我们来学习
函数的递归调用
什么是递归调用呢
就是函数自己调用自己
大家会不会觉得奇怪呀
什么时候会有这种情况呢
干吗会自己调用自己呢
实际上我们只要考虑一下
我们在数学中
在现实中一些
本来就存在的问题
你就会发现很多问题
它自己本就是递归的
用程序解决
当然也要用递归算法来解决
接下来
我们就来看看这个递归的问题
现在我们来看一下
这个函数递归调用的情况
函数它可以直接
或间接的调用自身
这个称为递归调用
现在我们来看一个
计算n的阶乘的例子
计算n的阶乘呢
当然我们可以用
不是递归的公式
比如说n的阶乘等于
n乘以n-1
乘以n-2 乘以n-3
一直乘2 乘以1
那n的阶乘
我们也可以用递归的公式
也就是说n的阶乘
它就等于n乘以n-1的阶乘
那么这样的公式
它本身就是一个递归的
也就是说
当你解释什么是阶乘的时候
又用到了阶乘
它的数据规模缩小了
它是n-1的阶乘了
照次下去
会数字越来越小 越来越小
总归到一个时刻
你能够计算出这个阶乘了
那比如说我们以4的阶乘为例
这就有一个递推的过程
那问我4的阶乘怎么做
我会告诉你
那就是4乘3的阶乘
那如果你再问3的阶乘
我也不会写
那我告诉你3的阶乘简单
那就是3乘以2的阶乘
你又问2的阶乘又是什么呢
2的阶乘是2乘1的阶乘
那1的阶乘又是什么
1的阶乘是1乘以0的阶乘
0的阶乘是几呢
这回我不再卖关子了
0的阶乘我告诉你 它就是1
如果是这样一个递推过程
结束了以后
我想你自然知道
怎么回推过去
就有个回归的过程
那由于你知道了0的阶乘是1
因此呢
我刚才告诉过你
1的阶乘怎么求
1的阶乘又求出来了
进而又求出了2的阶乘
3的阶乘
最后求出了4的阶乘
实际上这就是我们计算机程序
执行递归的代码的时候的
一个过程
递推和回归这样两个过程
现在我们来通过
求阶乘的这个函数
大家来体会一下
函数的递归调用
我们看这个函数
是一个求阶乘的函数
它接收一个参数n
也就是说要计算n的阶乘
那么n的阶乘是什么呢
它等于n乘以n-1的阶乘
也就是说这个函数
它的递归部分核心在这儿
将求n的阶乘
化简为成求n-1的阶乘
数据规模缩小了
但是并不是说
无穷无尽的递归
这有递归终结条件
大家看
当n等于0的时候
阶乘的值就是1了
我们在主函数中呢
从键盘输入一个n
然后用这个n作参数
去调用阶乘函数
下面我们运行一下看
进入主函数中
然后输入一个n
比如说我们来计算3的阶乘
输入一个3
好 现在我们来看
n的值是3了
接下来就要进入求阶乘的函数了
我们还是用f11追踪进去
进到这个阶乘函数里面
现在我们看调用栈
从主函数中
也就是程序第19行
开始调用阶乘函数的
现在目前在阶乘函数中
是第6行
那我们来看这个局部变量呢
n的值是3
要求3的阶乘
所以往下走
比较一下不是求0的阶乘
所以要走到else分支里面去
else分支就调用函数自身
但是数据规模有所缩小
继续追踪到函数里面去
又进到阶乘函数里面了
这一次n是2了 n的值是2
好 看调用栈
调用栈又多了一行
是在阶乘函数自己里面
也就是第11行的地方
调用了阶乘函数
那继续往下走
好 现在我们来看呢
又要再一次调用自身
那么这个时候
我们看它的局部变量
n是2
等它再次调用自身的时候
现在多少 n变成1了
所以每次用n-1去调用函数自身
进到函数里面
新的n的值就小了1
每次的数据规模减小1
好 我们继续往下执行
即使n等于1的时候
仍然没有到递归终结点
所以继续再次深入递归
这次进来的时候n等于0了
那我们看这个调用栈
一共多少次了
我们看到从主函数调了fun
fun的又调用了自己
再次调用了自己
然后又调用
最后一次调用自己
得到了f1的值
那么就要走到return
这个语句栈了
好 返回
返回到哪儿呢
应该返回到它的调用点
所以我们来看
返回到这个地方
调用栈退掉了一格
这个时候n是1了
从n等于0的那一次调用
退回了一级到n等于1的状态了
然后我们再看调用栈
在这儿就计算这个f的值
这一次就能把f的值计算出来
那么当前f的值是什么呢
是1
好 继续return 退
又退回到调用点
还是这个地方
那这回呢n是2了
再看调用栈又退掉了一格
再次计算f值
这次f的值计算了得2
再往回退
又退到调用点
这一次是n等于3的状态了
n等于3
刚刚计算完2的阶乘退回到这儿
那么2的阶乘乘以3
就得到3的阶乘
那我们看现在f得到了3的阶乘
看看调用栈的状态呢
目前只是从主函数中
调用了阶乘函数
目前存在于阶乘函数中
再一次退出的话
退到哪儿去呢
return 就退回到主函数中了
现在回到主函数当初的调用点
然后我们来看
这个阶乘函数的返回值是6
通过这个函数
我们就体会到函数的递归执行
它自身调用自身是怎么调用的
每一次调用的时候
数据规模应该缩小
从未知到已知
然后从已知再回退到未知
这么一个递推和回归
最终计算出最初未知数的
这么一个过程
好 这一节就到这儿
-导学
--第1章导学
-计算机系统简介
--计算机系统简介
--计算机系统简介 测试题
-计算机语言和程序设计方法的发展
--计算机语言和程序设计方法的发展 测试题
-面向对象的基本概念
--面向对象的基本概念 测试题
-程序的开发过程
--程序的开发过程
--程序的开发过程 测试题
-信息的表示和储存
--计算机的数字系统
--数据的编码表示
--信息的表示和储存 测试题
-实验指导
-导学
--第二章导学
-C++语言概述
--C++语言概述 测试题
-基本数据类型、常量、变量
--程序举例
--基本数据类型、常量、变量 测试题
-运算与表达式
--运算与表达式 测试题
-实验二:简单程序设计(上)
-数据的输入和输出
--数据的输入和输出
--数据的输入和输出 测试题
-选择结构
--if语句
--switch语句
--选择结构 测试题
-循环结构
--for语句
--循环结构 测试题
-自定义类型
--自定义类型
--自定义类型
-第2章小结
--第二章小结
-实验二:C++简单程序设计(下)
-导学
--导学
-函数定义
--函数定义
--函数定义 测试题
-函数调用
--例3-2
--例3-3
--例3-4
--例3-5
--例3-6
--函数调用 测试题
-嵌套与递归
--例3-9
--例3-10
--嵌套与递归 测试题
-函数的参数传递
--函数的参数传递
--函数的参数传递 测试题
-引用类型
--引用类型 测试题
-含有可变参数的函数
--含有可变参数的函数 测试题
-内联函数
--内联函数 测试题
-constexpr函数
--CONSTEXPR函数课后习题
-带默认参数值的函数
--带默认参数值的函数 测试题
-函数重载
--函数重载 测试题
-C++系统函数
--C++系统函数习题
-第3章小结
--第三章小结
-实验三(上)函数的应用
-实验三(下)函数的应用
-导学
--导学
-面向对象程序的基本特点
--面向对象程序的基本特点 测试题
-类和对象
--类和对象的定义
--类和对象 测试题
-构造函数
--构造函数基本概念
--委托构造函数
--复制构造函数
--构造函数 测试题
-析构函数
--析构函数
--析构函数 测试题
-类的组合
--类的组合
--类的组合程序举例
--前向引用声明
--类的组合 测试题
-UML简介
--UML简介
--UML简介课后习题
-结构体与联合体
--结构体与联合体 测试题
-枚举类
--枚举类
--枚举类 测试题
-第4章小结
--第四章小结
-实验四(上)
--实验四(上)
-实验四(下)
--实验四(下)
-导学
--导学
-标识符的作用域与可见性
--标识符的作用域与可见性 测试题
-对象的生存期
--对象的生存期
--对象的生存期 测试题
-类的静态成员
--类的静态成员 测试题
-类的友元
--类的友元 测试题
-共享数据的保护
--共享数据的保护 测试题
-多文件结构和预编译命令
--多文件结构和预编译命令 测试题
-第5章小结
--小结
-实验五
--实验五
-导学
--导学
-数组的定义与初始化
--数组的定义与使用
--一维数组应用举例
--数组的定义与初始化 测试题
-数组作为函数的参数
--数组作为函数的参数 测试题
-对象数组
--对象数组
--对象数组 测试题
-基于范围的for循环
-指针的定义和运算
--指针的定义和运算 测试题
-综合实例
--综合实例
-实验六(上)
--实验六上
-指针与数组
--指针数组
--指针与数组 测试题
-指针与函数
--指针类型的函数
--指向函数的指针
--指针与函数 测试题
-对象指针
--对象指针
--对象指针 测试题
-动态内存分配
--动态内存分配 测试题
-智能指针
--智能指针
-vector对象
--vector对象
--vector对象 测试题
-对象复制与移动
--移动构造
--对象复制与移动 测试题
-字符串
--C风格字符串
--string类
--字符串 测试题
-第6章小结
--第六章小结
-综合实例
--综合实例
-实验六(下)
--实验六(下)