尚义住房和城乡规划建设局网站,网络营销解决方案,网络推广软件赚钱,专业网站有哪些平台递归与回溯 To Iterate is Human, to Recurse, Divine. —L. Peter Deutsch 人理解迭代#xff0c;神理解递归。 —L. Peter Deutsch 1.什么是递归呢
递归形象描述#xff1a; 你打开面前这扇门#xff0c;看到屋里面还有一扇门。 你走过去#xff0c;发现手中的钥匙还可以…递归与回溯 To Iterate is Human, to Recurse, Divine. —L. Peter Deutsch 人理解迭代神理解递归。 —L. Peter Deutsch 1.什么是递归呢
递归形象描述 你打开面前这扇门看到屋里面还有一扇门。 你走过去发现手中的钥匙还可以打开它你推开门发现里面还有一扇门你继续打开它。 若干次之后你打开面前的门后发现只有一间屋子没有门了。 然后你开始原路返回每走回一间屋子你数一次走到入口的时候 你可以回答出你到底用这你把钥匙打开了几扇门。 2.递归算法Recursion
定义:直接或间接地出现对自身的调用。本质:递归即递进与回归,基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。但必须有一个明确的结束条件(递归出口) //斐波那契
int f(int n)
{if(n1)return 1;else if(n2)return 1;elsereturn f(n-1)f(n-2);
}利用递归完成的题目特点
可以将当前问题转换成规模更小的问题且新问题和原问题解法完全相同有一个明确的递归边界
3.递归案例
**用递归方法求**123……n
递归关系 f(n)f(n-1)n; 递归关系 f(1)1; 递归出口 用递归方法求n!
递归关系 f(n)f(n-1)*n; 递归关系 f(1)1; 递归出口 4.例题
王小二切饼
题目描述
王小二自夸刀工不错有人放一张大的煎饼在砧板上问他“饼不许离开砧板切n1n100)刀最多能分成几块
输入格式
输入切的刀数n
输出格式
输出切n刀最多切的块数
输入样例
3输出样例
7解题思路 杨辉三角 AC代码
#includebits/stdc.h
using namespace std;
int f(int x,int y)
{printf(调用f(%d,%d)\n,x,y);if(xy || y1)return 1;return f(x-1,y-1)f(x-1,y);
}
int main()
{int m,n;cinmn;coutf(m,n);return 0;
}5.程序分析 6.【背】核心代码模板
递归模板:
void recursion(大规模){if(end_condition){ //递归出口……return;}else{recursion(小规模); //递进,将大规模转换为小规模solve; //回归}
}7.总结
递归就是函数自己调用自己在递归过程中必须有一个明确的递归结束条件即递归出口每一次的函数调用都有自己的变量。每一次函数调用都会有一次返回。递归函数中位于递归调用前的语句和各级被调用函数具有相同的执行顺序。递归函数中位于递归调用后的语句和各个被调用函数的顺序相反。
优缺点 **优点**实现简单可读性好 **缺点**递归调用占用空间大递归太深易发生栈溢出可能会出现重复计算的问题(重叠子问题)
