当前课程知识点:C++语言程序设计基础 >  第3章 函数 >  嵌套与递归 >  函数的递归调用(例3-8)

返回《C++语言程序设计基础》慕课在线视频课程列表

函数的递归调用(例3-8)在线视频

函数的递归调用(例3-8)

函数的递归调用

 

定义

l   函数直接或间接地调用自身,称为递归调用。

 

例:计算n!

l  公式1:n!=n×(n-1)×(n-2)×(n-3)×...×2×1.

l  公式2:

 

例如,计算4!的两个阶段:

l  递推:

l  回归:



例3-8 求n!




 


源代码:#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


下一节:例3-9

返回《C++语言程序设计基础》慕课在线视频列表

函数的递归调用(例3-8)课程教案、知识点、字幕

大家好

欢迎继续学习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

通过这个函数

我们就体会到函数的递归执行

它自身调用自身是怎么调用的

每一次调用的时候

数据规模应该缩小

从未知到已知

然后从已知再回退到未知

这么一个递推和回归

最终计算出最初未知数的

这么一个过程

好 这一节就到这儿

C++语言程序设计基础课程列表:

第1章 绪论

-导学

--第1章导学

-计算机系统简介

--计算机系统简介

--计算机系统简介 测试题

-计算机语言和程序设计方法的发展

--计算机语言和程序设计方法的发展

--计算机语言和程序设计方法的发展 测试题

-面向对象的基本概念

--面向对象的基本概念

--面向对象的基本概念 测试题

-程序的开发过程

--程序的开发过程

--程序的开发过程 测试题

-信息的表示和储存

--计算机中的信息与存储单位

--计算机的数字系统

--数据的编码表示

--信息的表示和储存 测试题

-实验指导

--实验一:VS开发环境介绍

第2章 C++简单程序设计(一)

-导学

--第二章导学

-C++语言概述

--C++的特点和程序实例

--C++字符集和词法记号

--C++语言概述 测试题

-基本数据类型、常量、变量

--基本数据类型、常量、变量

--程序举例

--基本数据类型、常量、变量 测试题

-运算与表达式

--算术运算与赋值运算

--逗号运算、关系运算、逻辑运算和条件运算

--Sizeof运算、位运算

--运算优先级、类型转换

--运算与表达式 测试题

-实验二:简单程序设计(上)

--实验二:简单程序设计(上)

第2章 C++简单程序设计(二)

-数据的输入和输出

--数据的输入和输出

--数据的输入和输出 测试题

-选择结构

--if语句

--switch语句

--选择结构 测试题

-循环结构

--循环结构——while语句

--do-while语句

--for语句

--嵌套的控制结构、其他控制语句

--循环结构 测试题

-自定义类型

--自定义类型

--自定义类型

-第2章小结

--第二章小结

-实验二:C++简单程序设计(下)

--实验二C++简单程序设计(下)

第3章 函数

-导学

--导学

-函数定义

--函数定义

--函数定义 测试题

-函数调用

--函数调用(例3-1)

--例3-2

--例3-3

--例3-4

--例3-5

--例3-6

--函数调用 测试题

-嵌套与递归

--函数的嵌套调用(例3-7)

--函数的递归调用(例3-8)

--例3-9

--例3-10

--嵌套与递归 测试题

-函数的参数传递

--函数的参数传递

--函数的参数传递 测试题

-引用类型

--引用类型(例3-11)

--引用类型 测试题

-含有可变参数的函数

--含有可变参数的函数

--含有可变参数的函数 测试题

-内联函数

--内联函数(例3-14)

--内联函数 测试题

-constexpr函数

--constexpr函数

--CONSTEXPR函数课后习题

-带默认参数值的函数

--带默认参数值的函数

--默认参数值例(3-15)

--带默认参数值的函数 测试题

-函数重载

--函数重载(例3-16)

--函数重载 测试题

-C++系统函数

--C++系统函数(例3-17)

--C++系统函数习题

-第3章小结

--第三章小结

-实验三(上)函数的应用

--实验三(上)函数的应用

-实验三(下)函数的应用

--实验三(下)函数的应用

第4章 类与对象

-导学

--导学

-面向对象程序的基本特点

--面向对象程序的基本特点

--面向对象程序的基本特点 测试题

-类和对象

--类和对象的定义

--类和对象的程序举例

--类和对象 测试题

-构造函数

--构造函数基本概念

--构造函数例题(1)——例4-1

--构造函数例题(2)——例4-2

--委托构造函数

--复制构造函数

--复制构造函数调用举例

--构造函数 测试题

-析构函数

--析构函数

--析构函数 测试题

-类的组合

--类的组合

--类的组合程序举例

--前向引用声明

--类的组合 测试题

-UML简介

--UML简介

--UML简介课后习题

-结构体与联合体

--结构体(例4-7)

--联合体(例4-8)

--结构体与联合体 测试题

-枚举类

--枚举类

--枚举类 测试题

-第4章小结

--第四章小结

-实验四(上)

--实验四(上)

-实验四(下)

--实验四(下)

第5章 数据的共享与保护

-导学

--导学

-标识符的作用域与可见性

--标识符的作用域与可见性

--标识符的作用域与可见性 测试题

-对象的生存期

--对象的生存期

--对象的生存期 测试题

-类的静态成员

--静态数据成员(例5-4)

--静态函数成员(例5-5)

--类的静态成员 测试题

-类的友元

--类的友元(例5-6)

--类的友元 测试题

-共享数据的保护

--共享数据的保护(例5-7)

--共享数据的保护 测试题

-多文件结构和预编译命令

--多文件结构和预编译命令(例5-10)

--多文件结构和预编译命令 测试题

-第5章小结

--小结

-实验五

--实验五

第6章 数组、指针与字符串(一)

-导学

--导学

-数组的定义与初始化

--数组的定义与使用

--数组的储存与初始化

--一维数组应用举例

--数组的定义与初始化 测试题

-数组作为函数的参数

--数组作为函数参数(例6-2)

--数组作为函数的参数 测试题

-对象数组

--对象数组

--对象数组 测试题

-基于范围的for循环

--基于范围的for循环

-指针的定义和运算

--指针的概念、定义和指针运算

--指针的初始化和赋值

--指针的算术运算、关系运算

--指针的定义和运算 测试题

-综合实例

--综合实例

-实验六(上)

--实验六上

第6章 数组、指针与字符串(二)

-指针与数组

--用指针访问数组元素

--指针数组

--指针与数组 测试题

-指针与函数

--以指针作为函数参数

--指针类型的函数

--指向函数的指针

--指针与函数 测试题

-对象指针

--对象指针

--对象指针 测试题

-动态内存分配

--动态分配与释放内存

--申请和释放动态数组(一)

--申请和释放动态数组(二)

--动态内存分配 测试题

-智能指针

--智能指针

-vector对象

--vector对象

--vector对象 测试题

-对象复制与移动

--深层复制与浅层复制

--移动构造

--对象复制与移动 测试题

-字符串

--C风格字符串

--string类

--字符串 测试题

-第6章小结

--第六章小结

-综合实例

--综合实例

-实验六(下)

--实验六(下)

函数的递归调用(例3-8)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。