-
2021-12-14 15:04:50
1.递归实现冒泡排序
list = [1,5,2,3,6,8,5,4,7,88,77,55,99,88,55] def bub_list(s_list): #代表无数据交换 flag = 0 for i in range(len(s_list) - 1): if s_list[i] > s_list[i+1]: flag = 1 s_list[i],s_list[i+1] = s_list[i+1],s_list[i] #判断flag的值如果等于1 具有表示交换的值 就要调用bub_list if flag == 1: bub_list(s_list) else: s_list # bub_list(list) # # print(list)
2.非递归实现冒泡排序
#非递归实现冒泡排序 def bus_list(s_list): for i in range(len(s_list)): flag = 1 for j in range(len(s_list) -1-i):#代表内循环次数 if s_list[j] > s_list[j+1]: #开始交换 s_list[j],s_list[j+1] = s_list[j+1],s_list[j] flag = 0 if flag:#如果已经有 则跳出循环 break return s_list # # bus_list(list) # # print(list)
更多相关内容 -
C++ 中快排的递归和非递归实现
2020-08-30 06:07:53主要介绍了C++ 中快排的递归和非递归实现的相关资料,需要的朋友可以参考下 -
递归实现字符串模糊匹配.java
2020-12-26 08:44:27使用递归实现,字符串模糊匹配,看设置允许匹配错误数。 -
MyBatis之自查询使用递归实现 N级联动效果(两种实现方式)
2020-08-30 00:09:22主要介绍了MyBatis之自查询使用递归实现 N级联动效果,本文给大家分享两种实现方式,需要的的朋友参考下吧 -
使用递归实现n重for循环
2019-03-26 14:56:51使用递归的方式来替代for来实现不同行与行之间进行组合。 输入(1,2,3)(4,5,6) 得到 (1 4)(1 5)(1 6)(2 4)(2 5)(2 6)(3 4)(3 5)(3 6) -
全排列的非递归实现JAVA
2019-03-27 00:18:34全排列的非递归实现。 输入1,2,3,4 得到 [1 2 3 4]..........[4 3 2 1]所有24种排列 -
递归实现遍历目录下子所有目录内所有文件
2019-02-27 21:57:45递归实现遍历目录下子所有目录内所有文件 -
C++ 中二分查找递归非递归实现并分析
2020-08-30 08:15:17主要介绍了C++ 中二分查找递归非递归实现并分析的相关资料,需要的朋友可以参考下 -
全排列算法的非递归实现与递归实现的方法(C++)
2020-09-05 07:57:36本篇文章是对全排列算法的非递归实现与递归实现的方法进行了详细的分析介绍,需要的朋友参考下 -
Java编程二项分布的递归和非递归实现代码实例
2020-08-28 04:37:35主要介绍了Java编程二项分布的递归和非递归实现代码实例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下 -
八皇后递归及非递归实现源码
2018-01-03 17:19:19八皇后递归及非递归实现源码; 八皇后递归及非递归实现源码 -
递归实现字符串逆序
2014-09-14 16:25:25c++实现的关于递归实现逆序字符串,有需要的可以下载 -
格雷码的递归实现代码(极简)
2015-09-06 23:05:04最近不少面试问到格雷码的递归问题,写了个用递归方式实现格N位雷码的产生于输出,程序代码量很少,可以直接运行。可以下载看看。 -
Java中的递归详解(用递归实现99乘法表来讲解)
2020-09-03 20:48:19主要介绍了Java中的递归详解(用递归实现99乘法表来讲解),本文给出了普通的99乘法实现方法和用递归实现的方法,并对比它们的不同,体现出递归的运用及理解,需要的朋友可以参考下 -
Vue结合路由配置递归实现菜单栏功能
2020-10-15 05:10:39主要介绍了Vue结合路由配置递归实现菜单栏,本文通过实例代码给大家介绍的非常详细,对大家的学习火锅工作具有一定的参考借鉴价值,需要的朋友可以参考下 -
先序遍历二叉树的递归实现与非递归实现深入解析
2020-09-05 02:45:44以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下 -
JAVA递归与非递归实现斐波那契数列
2020-08-28 01:38:37主要为大家详细介绍了JAVA递归与非递归实现斐波那契数列,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
Python用递归实现字符串反转
2014-10-08 14:10:09手动输入一个字符串,Python用递归实现字符串反转 -
快速排序的递归实现和非递归实现
2021-02-19 21:59:46一、快速排序的递归实现 快速排序的思想是每次找到一个元素的位置,再在以这个元素分隔的两个子范围中分别再各自确定一个元素的位置,子子范围也是如此操作,当某个子范围只有一个元素或者没有元素时,便不再做任何...一、快速排序的递归实现
快速排序的思想是每次找到一个元素的位置,再在以这个元素分隔的两个子范围中分别再各自确定一个元素的位置,子子范围也是如此操作,当某个子范围只有一个元素或者没有元素时,便不再做任何操作。这是一个递归过程,递归退出的边界就是子范围中不存在元素或者只存在一个元素。
基于这个思想,很容易便得到递归处理的程序框图:
代码:#include <cstdio> using namespace std; static void quickSort(int array[],int low,int high){ int l=low,h=high,tmp; if (l<h){ tmp=array[l]; while (l<h){ while (array[h]>=tmp){ h--; if(l == h){ goto complete; } } array[l]=array[h]; while (array[l]<tmp){ l++; if(l == h){ goto complete; } } array[h]=array[l]; } complete: array[l]=tmp; //递归处理左右的序列 quickSort(array,low,l-1); quickSort(array,h+1,high); } } int main() { //测试 int a[8]={49,38,65,97,76,13,27,49}; quickSort(a,0,7); for (int i = 0; i < 8; i++) { printf("%d ",a[i]); } return 0; }
二、快速排序的非递归实现
上述递归实现的局限性可能在于:当数据量特别大时,可能会导致栈溢出(栈涨的速度为 log 2 n \log_2n log2n,也可能是我多虑了,涨地其实挺慢的)。
为了解决上面可能出现的问题,我们可以将递归实现转换为非递归实现,我们知道任何递归的过程都可以转化为一个迭代的过程,而转化的关键在于如何使用迭代来模拟整个递归的处理。
观察上面的递归处理过程,我们可以看到:每一次排序函数的调用都会再次重新调用两次新的排序函数,然后系统会按照调用顺序一步一步地进行处理和返回,而调用排序函数的关键在于必须将排序的范围告诉函数。
这个过程很像一个排队处理的过程,于是我们可以使用队列进行递归的模拟,而队列中的信息存储要处理的范围即可。当队列不为空时,表示还有范围未处理;队列为空时,表示所有的范围都已经处理完毕,也即确定了所有元素的位置,完成了排序工作。
于是我们可以得到下面非递归处理的程序框图:
代码:#include <cstdio> #include <queue> using namespace std; struct Scope{ int low,high; }; static void quickSort2(int array[],int low,int high){ queue<Scope> scopes; scopes.push({low,high}); Scope sp; while (!scopes.empty()){ sp = scopes.front(); scopes.pop(); int l=sp.low,h=sp.high,tmp; if (l<h){ tmp=array[l]; while (l<h){ while (array[h]>=tmp){ h--; if(l == h){ goto complete; } } array[l]=array[h]; while (array[l]<tmp){ l++; if(l == h){ goto complete; } } array[h]=array[l]; } complete: array[l]=tmp; //将左右子序列加入待处理队列中 scopes.push({sp.low,l-1}); scopes.push({h+1,sp.high}); } } } int main() { //测试 int a[8]={49,38,65,97,76,13,27,49}; quickSort2(a,0,7); for (int i = 0; i < 8; i++) { printf("%d ",a[i]); } return 0; }
-
PHP利用递归实现分类树显示
2020-05-14 16:21:22php利用递归实现分类树显示(使用递归实现分类树显示,要写好多字哟能不能少写点,复制几行凑数,使用递归实现分类树显示使用递归实现分类树显示使用递归实现分类树显示) -
数据结构-二叉树递归-非递归实现
2021-04-26 20:35:46数据结构实验二叉树用递归实现先序遍历、中序遍历和后序遍历,用几种不同非递归方法实现了中序遍历,代码附有详细注释 -
递归算法的非递归实现
2021-02-28 22:14:13背景 最近做题遇到过几次递归实现的算法,要求你用非递归的方式实现。这里做一个总结。其实也没技巧,再看几遍,多默写几次代码,记熟即可。 递归算法基本都涉及到函数调用栈。每次递归调用时都将函数数据入栈,...栈的作用
当前问题执行到一个状态,以现有的条件无法完全解决时,必须先记下当前状态,然后继续往下执行,等条件成熟后再返回解决。
如DFS时,当前节点1,沿着邻接点2往下遍历,后面还要回到节点1继续遍历其他邻接点。背景
最近做题遇到过几次递归实现的算法,要求你用非递归的方式实现。这里做一个总结。其实也没技巧,再看几遍,多默写几次代码,记熟即可。
递归算法基本都涉及到函数调用栈。每次递归调用时都将函数数据入栈,所以递归调用越深,占用的栈空间越多。如果层数过深,肯定会导致栈溢出,这也是消除递归的必要性之一。1. 直接转换法
用循环结构代替单向递归和尾递归。
单向递归:简单的说是指递归的过程总是朝着一个方向进行。函数1调用函数2再调用函数3…一只不重复调用之前的函数。
尾递归函数是以递归调用结尾的函数,是单向递归的特例。尾递归的递归调用语句只有一个,而且是放在过程的最后。当递归调用结束并返回时,上层函数也就结束了。无需关注函数地址、参数、局部变量等,因此可以直接采用循环写出非递归过程。
斐波那契数列的递归
int Fib(int n) { if (n<=1) return n; else return Fib(n - 1) + Fib(n - 2);//尾递归调用 }
斐波那契数列的非递归
int Fib(int n) { if (n<=1) return n; else//循环实现 int x1= 1; int x2= 0; int sum; for(int i = 2;i < = n; i++) { sum= x1+x2; x2= x1; x1= sum; } return sum; }
如何由递归转循环呢,我的思路是列出递归每次的值,然后找规律:
0 1 1
n x1 x2 SUM 0 A B 0 1 C D 1 2 1 0 1 3 1 1 2 4 2 1 3 5 3 2 5 6 5 3 8 0、1的时候直接是n,因此循环从2开始,x1初始为0,x2初始为1;依次递增到n(n>=2)结束,执行n-1次 int x1= 1; int x2= 0; int sum; for(int i=2;i<=n;++i)
再观测,x2等于上一次相加的x1,x1等于上一次相加的sum。则循环体内为:
sum= x1+x2; x2= x1; x1= sum;
直接用循环替代递归不是很难,一般找清楚递归的变化规律就可以做出。
2. 间接转换法
用于需要回溯的递归;如:函数1调用函数2,函数2又要回溯到函数1;再由函数1调用函数3;(想象树的遍历)我们可以根据函数调用栈,手动建立一个栈,实现非递归实现。
int Stack[Maxsize],top=-1 visit(a); Stack(++top)=a//将初始状态a进栈 while(top!=-1)//栈不为空 { a1=Stack(top);//将栈顶元素赋给a1 //从a1中寻找满足条件的a2 if(a2 true)//找到了 { visit(a2);//访问a2; Stack(++top)=a2;//将a2进栈 } else//未找到,a1遍历完毕 ---top;//a1退栈 }
注意一点就是:先读取栈顶元素,找到栈顶元素满足条件的下一个元素入栈。因为此时该元素没有出栈+循环的缘故,上层栈内元素出栈后,会回溯到该元素,直到该元素所有满足条件的元素都被访问,该元素出栈,就不会被回溯。这就模拟了函数的递归调用栈。
在数据结构中递归间接转换非递归应该有很多,不够我目前遇到的主要还是二叉树遍历和图的深度遍历,下面做一个记录:二叉树先序遍历
void preorder(BTNode *p) { if(p!=NULL) { visit(p); preorder(p->lchild); preorder(p->rchild); } }
先序遍历
观察先序遍历的入栈过程:
根节点入栈并访问
根节点左子树各节点入栈并访问,各节点出栈
根节点右子树各节点入栈并访问,各节点出栈
根节点出栈void preorder(BTNode *bt) { if(bt!=NULL) { BTNode *STack[Maxsize]; int top=-1; BTNode *p; Stack[++top]=bt; while(top!=-1) { p=Stack[top--]; visit(p); if(p->rchild!=NULL) Stack[++top]=p->rchild; if(p->;child!=NULL) Stack[++top]=p->rchild; } } }
模拟先序遍历:
根节点入栈
循环
-----栈顶元素出栈,访问;
-----栈顶元素右孩子入栈;左孩子入栈;
直到栈空注意:真实递归的话是左子树先入栈,依次遍历并出栈后右子树才入栈。
我们这边模拟为了简化,是右孩子先入左孩子后入。以此实现先访问左孩子后访问右孩子。中序:
while(top!=-1||p!=NULL)//存在节点出栈后栈空(根节点),但是p非空,右子树还可以入栈。 { while(p!=NULL)//一直向左入栈,直到节点没有左孩子 { Stack[++top]=p; p=p->lchild; } if(top!==-1)//节点出栈,访问,右孩子 { p=Stack[top--]; visit[p]; p=p->rchild; } }
节点入栈时,节点左孩子入栈;
直到节点左孩子不存在,节点出栈,节点右孩子入栈;
直到栈空后序:
while(top!=-1)//按根右左入栈1 { p=Stack1[top1--]; Stack2[++top2]=p;//每次栈顶元素出栈都入栈2 if(p->lchild!=NULL) Stack1[++top1]=p->lchild; if(p->rchild!=NULL) Stack1[++top1]=p->rchild; } whild(top2!=-1)//栈2就是根右左的逆序————>左右根 { p=Stack2[top2--]; visit(p); }
栈1中根右左顺序入栈2
栈2中即可实现逆序,左右根深度遍历
DFS(G,V){ ...... visit(v) visited[v]=1; for(w=g->adjlist[v1].firstarc;w!=NULL;w=w->nextarc) { if(visited[w]!=1) { DFS(g,w->adjvex); } } }
访问v0;v0此时已在函数栈中
找v0的第一个为未访问的边;
找到就递归调用边指向的邻接点v1访问邻接点v1;邻接点v1此时已在函数栈中
找v1的第一个为未访问的边;
找到就递归调用边指向的邻接点v2
没有找到就结束递归,v2出栈回溯访问v0;v0此时还在函数栈中
找v0的第一个为未访问的边;(此时指向v1的边已经访问了)
找到就递归调用边指向的邻接点v3int Stack[Maxsize],top=-1 visit(v);//访问第一个结点 visited[v]=1; Stack(++top)=v//将初始结点进栈 while(top!=-1)//栈不为空 { v1=Stack(top);//将栈顶元素赋给v1 p=g->adjlist[v1].firstarc;//该结点的第一条边 while(p!=NULL&&visited[p->adjvwx]=1)//遍历该结点的adjlist,找到第一个未访问的邻接点 p=p->nextarc; if(p==NULL)//遍历结束,该结点的所有邻接点都访问了 ---top;//该结点退栈 else//找到邻接点 { visit(p->adjvex);//访问邻接点 visited[p->adjvex]=1; Stack(++top)=p->adjvex;//将邻接点入栈 } }
访问v0并入栈;
提取栈顶v0;找v0的第一个未访问的边;
找到了;访问边指向的邻接点v1并入栈
没找到;V0出栈参考
[1] https://blog.csdn.net/fbz123456/article/details/50959412.
新开通了本人的公众号,欢迎关注:燕南路GISer ,专注GIS干货分享,不定期更新。
主要兴趣:GIS、时空数据挖掘、python、机器学习深度学习
提问、求资源等都可在公众号后台留言
CSDN的部分内容会重写再搬迁到公众号,欢迎关注!
-
归并排序的递归实现与非递归实现代码
2020-09-05 02:16:27以下是对归并排序的递归实现与非递归实现代码进行了详细的介绍,需要的朋友可以过来参考下 -
用递归实现1加到100
2014-08-11 16:08:24用递归的方法实现1加到100,新颖的做法 -
java递归实现树(Tree)
2013-12-25 23:36:45一个简单的小例子递归实现list按照index排序的树 -
递归函数 以及递归实现数组扁平化 和递归实现深拷贝
2021-11-30 17:04:291.递归函数:在函数内部自身调用自身的函数。 2. //方法: 1:找临界值:无须计算,即可得出的值:---退出递归的条件 2:这一次和上一次运算的关系fn和fn-1的关系 3:假设当前递归函数可以运行,根据上一次...1.递归函数:在函数内部自身调用自身的函数。
2.
// 方法:
1:找临界值:无须计算,即可得出的值:---退出递归的条件
2:这一次和上一次运算的关系 fn和fn-1的关系
3:假设当前递归函数可以运行,根据上一次调用自身的结果,写出这次运算的结果。f(n)=f(n-1)+n=>f(10)=f(9)+10=f(8)+10+9
下面用递归 做几道题帮助理解
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> </head> <body> </body> <script> // 递归函数:在函数内部自身调用自身的函数。 // 循环能做的所有事情 递归都能做 // 循环做不了的事情 递归也能做 // 方法: // 1:找临界值:无须计算,即可得出的值:---退出递归的条件 // 2:这一次和上一次运算的关系 fn和fn-1的关系 // 3:假设当前递归函数可以运行,根据上一次调用自身的结果,写出这次运算的结果。f(n)=f(n-1)+n=>f(10)=f(9)+10=f(8)+10+9 // 列: // 传入一个n,打印n个hello world 递归 // f(n)=f(n-1)+console.log("hello world") // function printHello(n){ // if (n==1) { // console.log("hello world") // return ; // } // console.log("hello world") // return printHello(n-1); // } // printHello(5) // 兔子繁殖问题:设有一对新生兔子,从第四个月开始他们每个月月初都生一对兔子,新生的兔子从第四个月月初开始又每个月生一对兔子 // 按此规律,并假定兔子没有死亡,n(n <= 20)个月月末共有多少对兔子? // 规律: 月份 1 2 3 4 5 6 7 8 9 10 ... // 兔子 1 1 1 2 3 4 6 9 13 19 // 规律: f(n) = f(n-1)+f(n-3) // function rabbits(n) { // if (n <= 3) { // return 1; // } // return rabbits(n - 1) + rabbits(n - 3); // } // console.log(rabbits(20)) // console.log(rabbits(10)) // 猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个,第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃前一天剩下的一半零一个。 // 到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘多少个桃子? // 10 9 8 7 6 5 4 3 2 1 // 1 4 10 22 46 94 190 382 766 1534 // var sum = 1; // for (var i = 1; i < 10; i++) { // sum =(sum+1)*2; // } // console.log(sum) // 规律: f(n) = (f(n+1)+1)*2 // function getTotal(n) { // if (n == 10) { // return 1; // } // return (getTotal(n + 1) + 1) * 2; // } // console.log(getTotal(1)) </script> </html>
3.递归实现深拷贝
深拷贝请看 个人另一篇文章 有详细解说
function deepClone(obj = {}) { if (typeof obj !== 'object' || obj == null) { // obj 是 null ,或者不是对象和数组,直接返回 return obj } // 初始化返回结果 let result if (obj instanceof Array) { result = [] } else { result = {} } for (let key in obj) { // 保证 key 不是原型的属性 if (obj.hasOwnProperty(key)) { // 递归调用!!! result[key] = deepClone(obj[key]) } } // 返回结果 return result }
4.递归实现数组扁平化
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>数组扁平化</title> </head> <body> </body> <script type="text/javascript"> // 数组扁平化概念:数组扁平化是指将一个多维数组变为一维数组 // [1, [2, 3, [4, 5]]] ------> [1, 2, 3, 4, 5] // 5种方式实现数组扁平化 var arr = [1, [2, 3, [4, 5, [6, 7, 8, [9, 10]]]]] // flat 扁平化 Infinity number 无穷大 // console.log(arr.flat(Infinity)) // 注意:flat和flatMap方法为ES2019(ES10)方法,目前还未在所有浏览器完全兼容。 // function flatten1(arr){ // return arr.flat(Infinity) // } // console.log(flatten1(arr)) // 1.递归实现数组扁平化 递归的遍历每一项,若为数组则继续遍历,否则concat 重点 // function flatten(arr) { // var result = []; // arr.map(item => { // if (Array.isArray(item)) { // result = result.concat(flatten(item)) // } // // 不是数组 // else { // result.push(item) // } // }) // return result // } // console.log(flatten(arr)) // 2. reduce:遍历数组每一项,若值为数组则递归遍历,否则concat。 // function flatten4(arr) { // return arr.reduce((result, item)=> { // return result.concat(Array.isArray(item) ? flatten4(item) : item); // }, []); // } // console.log(flatten4(arr)) // 总结:遍历数组arr,若arr[i]为数组则递归遍历,直至arr[i]不为数组然后与之前的结果concat。 </script> </html>
-
C语言数据结构中二分查找递归非递归实现并分析
2020-08-31 01:58:41主要介绍了C语言数据结构中二分查找递归非递归实现并分析的相关资料,需要的朋友可以参考下 -
汉诺塔的非递归实现,c++
2012-08-22 15:25:28汉诺塔的非递归实现,c++实现的,很简单,只有50多行,从递归的汉诺塔改编而来,将原来递归时的参数状态保存在栈中,入栈代替递归,出栈代替递归返回。 -
用递归实现冒泡排序
2020-11-19 10:24:25用递归实现冒泡排序 本文内容如标题所示,用递归实现冒泡排序,相信你对冒泡排序不陌生,也实现过,不知道你用递归实现过没?下面就看下其代码: //用递归实现输出数组 void output(int arr[], int n){ static ...