做国外单的网站叫什么名字,西安 内部网站建设,网站后台制作步骤,小程序头条小游戏#x1f34e; 博客主页#xff1a;#x1f319;披星戴月的贾维斯 #x1f34e; 欢迎关注#xff1a;#x1f44d;点赞#x1f343;收藏#x1f525;留言 #x1f347;系列专栏#xff1a;#x1f319; 蓝桥杯 #x1f319;我与杀戮之中绽放#xff0c;亦如黎明的花… 博客主页披星戴月的贾维斯 欢迎关注点赞收藏留言 系列专栏 蓝桥杯 我与杀戮之中绽放亦如黎明的花朵 一起加油去追寻、去成为更好的自己 蓝桥杯倒计时 37天 文章目录、递归算法、例题分析、AcWing递归实现指数型枚举、AcWing递归实现排列型枚举、AcWing树的遍历、总结提示以下是本篇文章正文内容下面案例可供参考 、递归算法
、递归的概念 递归算法英语recursion algorithm在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环因此在很多函数编程语言如Scheme中习惯用递归来实现循环。(来源百度百科) 、递推的简单例子 1、求阶乘的函数就是递归调用自己的一个简单的例子 int fact(int x)
{if(n 0) return 1;else return n n * fact(n - 1);
}2、斐波那契数列也是一个简单的递归调用自身的例子 int fbnq(int n)
{if (n 1 || n 2) return 1;if(n 2)return (fbnq(n - 1) fbnq(n - 2));
}3、我们在构建树以及深度优先搜索时都会用到递归。每一棵树都对应这一种递归。 void dfs(int u)
{if(满足条件)dfs(u 1);
}、递推示例图
、例题分析
、AcWing递归实现指数型枚举
本题链接: 递归实现指数型枚举 分析题意 代码示例
#includeiostream
#includecstdio
#includecstring
using namespace std;
const int N 20;
int n;
bool st[N];
void dfs(int u)
{if(u n){for(int i 1; i n; i)if(st[i])cout i ;puts();return;}st[u] false;//第一个分支不选dfs(u 1); //往下一层递归st[u] true;//恢复现场dfs(u 1);
}
int main ()
{cin n;dfs(1);return 0;
}、AcWing递归实现排列型枚举
本题链接: 递归实现排列型枚举 分析题意 代码示例
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n;
const int N 10;
int st[N];
bool used[N];
void dfs(int u)
{if(u n){for(int i 1; i n; i)printf(%d , st[i]);puts();return;}for(int i 1; i n; i)if(!used[i])//没用过{st[u] i;//没用过填进去used[i] true;//表示用过了dfs(u 1);//递归到下一位st[u] 0;//恢复现场used[i] false;//回溯}
}int main ()
{cin n;dfs(1);return 0;
}、AcWing树的遍历
本题链接: 树的遍历
#includeiostream
#includevector
#includealgorithm
#includecstring
using namespace std;
const int N 35;
int a[N], b[N], p[N]; //a表示后序遍历b表示中序遍历p存储中序遍历每一个下标的位置。
int n;
vectorint level[N];
void build(int al, int ar, int bl, int br, int d) // 递归构建子树。
{if(al ar) return;int val a[ar]; //根结点的权值 level[d].push_back(val);int k p[val]; //求一下根结点的权值在中序遍历里面的下标build(al, al k - 1 - bl, bl, k - 1, d 1);build(al k -bl, ar - 1, k 1, br , d 1);
}
int main()
{cin n;for(int i 0; i n; i) cin a[i];for(int i 0; i n; i) cin b[i];for(int i 0; i n; i) p[b[i]] i;//记录每一个数值在中序遍历里的位置build(0, n - 1, 0, n-1, 0);for(int i 0; i n; i)for(auto c: level[i])cout c ;return 0;
}、总结 本文简要介绍了递归算法的简要概念和几道递归算法的经典例题希望大家读后能有所收获
