算法基础3 —— 递归(上)
2021/6/6 12:22:28
本文主要是介绍算法基础3 —— 递归(上),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
递归
递归是算法竞赛中的难点。传说人可以理解迭代,神理解递归。
To Iterate is Human, to Recurse, Divine. —L. Peter Deutsch
定义
直接或间接地出现对自身的调用。
本质
递归 = 递进 + 回归
(递进与回归缺一不可)
基本思想
把规模大的问题转化为规模小的相似的子问题来解决,且必须有一个明确的结束条件即递归出口
例1
求等差数列1,2,3,4,5,… …的第n项的值
(注:使用递归时需要写出递归表达式,而递归表达式 = 递归关系 + 递归出口)
代码如下:
#include <iostream> using namespace std; int f(int n) { if (n == 1) return 1;//递归出口 else return f(n - 1) + 1;//递归关系:后一项等于前一项的值加1 } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }
同理,如果要求数列1,3,5,7,9,11… …中第n项的值,只需要把递归关系改为return f(n - 1) + 2;
即可
递归过程如下所示:
例2 Fibonacci数列
1,1,2,3,5,8,13,21… …
#include <iostream> using namespace std; int f(int n) { if (n == 1 || n == 2) return 1;//递归出口 else return f(n - 1) + f(n - 2);//递归关系 } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }
总结:利用递归完成的题目特点
- 可以将当前问题转换成规模更小的问题,且新问题和原问题解法完全相同
- 有一个明确的递归边界
例3 :用递归方法求:1+2+3+……+n
(本题为中国矿业大学2021年考研初试题,很多同学以往用for循环完成本题,而疏于锻炼递归思想)
代码如下
#include <iostream> using namespace std; //Sum(n)表示数列前n项的和 int Sum(int n) { if (n == 1) return 1;//递归出口 else return Sum(n - 1) + n;//递归关系 } int main() { int n; cin >> n; cout << Sum(n) << endl; return 0; }
例4 : 用递归方法求n!
#include <iostream> using namespace std; int f(int n) { if (n == 1) return 1;//递归出口 else return f(n - 1) * n;//递归关系 } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }
例5 : 王小二切饼
有一张大的煎饼在砧板上,饼不许离开砧板,切n(1<=n<=100)刀最多能将饼分成几块?
输入格式:输入切的刀数n
输出格式:输出切n刀最多切的块数
输入样例:3
输出样例:7
分析:
如图所示,切1刀最多可以将饼分成2块:
切2刀最多可以将饼分成4块:
切3刀最多可以将饼分成7块:
切4刀最多可以将饼分成11块:
不难发现:
- 要想将饼的块数切的较多,需要满足切割线两两相交且没有交点
- 第1刀 —— 2块;
- 第2刀 —— 4块;(2 + 2)
- 第3刀 —— 7块;(3 + 4)
- 第4刀 —— 11块;(4 + 7)
- … …
- 设第n-1刀 —— i块;
- 则第n刀 ——(n+i)块;
设切第n刀可以得到f(n)块饼,由此得到递归表达式:
if (n == 1) return 2;
else return f(n - 1) + n;
代码如下:
#include <iostream> using namespace std; int f(int n) { if (n == 1) return 2;//递归出口 else return f(n - 1) + n;//递归关系 } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }
这篇关于算法基础3 —— 递归(上)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南