当前课程知识点:C++语言程序设计基础 > 第3章 函数 > 嵌套与递归 > 例3-9
大家好
欢迎继续学习C++语言程序设计
这一节呢
我要给大家介绍一个
典型的递归的例题
这个例题要求我们
从n个人里面
选择k个人组成一个委员会
这是一个典型的组合问题
这个问题本身
我相信大家都见过
那么用计算机程序
怎么去实现这个问题呢
那我们就要看看组合的公式本身
大家想想这个问题
要用组合来解决吧
那么组合的公式描述
是不是本身就是递归的呢
好 现在我们来看
这个从n个人里面
选k个人组成委员会的这个例题
它的公式实际上是这样的
这是一个大家学过的
在数学中学过的组合的公式
也就是由n个人里
选k个人的组合数
等于由n-1个人里
选k个人的组合数
加上由n-1个人里面
选k-1个人的组合数
那也就是说
我们看到它又是一个递归的问题
在解释什么是组合的时候
又用到了组合
所以后面给出的这个条件
非常重要
必须有这个递归终结条件
就是当n等于k
或者k等于0的时候
组合数为1
如果没有这个递归终结条件的话
这个递归将无穷无尽
这个公式就不可计算了
下面我们来看
这个代码的实现
这个函数也是一个递归函数
我们来看
这个函数里面
它有两个深入递归点
由于组合的公式
又用到了组合
所以我们来看
从n个人里面
选k个人组成委员会的这个函数
如果n大于k 那么方案为0
所以return 0没有选法
如果说n等于k
或者k等于0
那只有一种选法
所以结论是1
不要小看这个结论1
恰恰这个是递归的终结点
好 那么如果都不是这两种情况
那就进到最后一个else分支里面
要调用自身去求
从n-1个人里面选k个人
和从n-1个人里面选k-1个人
把它们两个加起来
所以解决组合问题的时候呢
又用到了这个组合函数
那么这个函数它比较复杂
因为它有两个递归深入点
在第一个递归深入点
深入递归
再回退回原来的位置以后
又要进到第二个递归深入点
再深入递归进去
再回退回来
这个呢
我希望大家用单步跟踪的方式
跟踪这个递归过程
看一看这个结果
数不要选的太大
递归的层不要太多
重点是要体会一下
这个深入递归
和逐级回退的这个过程
那么主函数的逻辑
当然是比较简单
直接调用这个组合函数就可以了
只是在执行组合函数的过程中
它的过程是一个递归的过程
好 这个例题就是这些内容
-导学
--第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章小结
--第六章小结
-综合实例
--综合实例
-实验六(下)
--实验六(下)