阅读下列递归算法，写出非递归方法实现相同功能的c程序？

来源：蜘蛛抓取(WebSpider) 时间：2022-06-22 10:50 标签： 折半查找非递归

当前问题执行到一个状态，以现有的条件无法完全解决时，必须先记下当前状态，然后继续往下执行，等条件成熟后再返回解决。
如DFS时，当前节点1，沿着邻接点2往下遍历，后面还要回到节点1继续遍历其他邻接点。

最近做题遇到过几次递归实现的算法，要求你用非递归的方式实现。这里做一个总结。其实也没技巧，再看几遍，多默写几次代码，记熟即可。
递归算法基本都涉及到函数调用栈。每次递归调用时都将函数数据入栈，所以递归调用越深，占用的栈空间越多。如果层数过深，肯定会导致栈溢出，这也是消除递归的必要性之一。

用循环结构代替单向递归和尾递归。

单向递归：简单的说是指递归的过程总是朝着一个方向进行。函数1调用函数2再调用函数3…一只不重复调用之前的函数。
尾递归函数是以递归调用结尾的函数，是单向递归的特例。

尾递归的递归调用语句只有一个，而且是放在过程的最后。当递归调用结束并返回时，上层函数也就结束了。无需关注函数地址、参数、局部变量等，因此可以直接采用循环写出非递归过程。

如何由递归转循环呢，我的思路是列出递归每次的值，然后找规律：

0 0
0
0、1的时候直接是n,因此循环从2开始，x1初始为0，x2初始为1；依次递增到n（n>=2)结束，执行n-1次

再观测，x2等于上一次相加的x1，x1等于上一次相加的sum。则循环体内为：

直接用循环替代递归不是很难，一般找清楚递归的变化规律就可以做出。

用于需要回溯的递归；如：函数1调用函数2，函数2又要回溯到函数1；再由函数1调用函数3；（想象树的遍历）我们可以根据函数调用栈，手动建立一个栈，实现非递归实现。

注意一点就是：先读取栈顶元素，找到栈顶元素满足条件的下一个元素入栈。因为此时该元素没有出栈+循环的缘故，上层栈内元素出栈后，会回溯到该元素，直到该元素所有满足条件的元素都被访问，该元素出栈，就不会被回溯。这就模拟了函数的递归调用栈。
在数据结构中递归间接转换非递归应该有很多，不够我目前遇到的主要还是二叉树遍历和图的深度遍历，下面做一个记录：

观察先序遍历的入栈过程：
根节点左子树各节点入栈并访问，各节点出栈
根节点右子树各节点入栈并访问，各节点出栈

-----栈顶元素出栈，访问；
-----栈顶元素右孩子入栈；左孩子入栈；

注意：真实递归的话是左子树先入栈，依次遍历并出栈后右子树才入栈。
我们这边模拟为了简化，是右孩子先入左孩子后入。以此实现先访问左孩子后访问右孩子。

节点入栈时，节点左孩子入栈；
直到节点左孩子不存在，节点出栈，节点右孩子入栈；

栈1中根右左顺序入栈2
栈2中即可实现逆序，左右根

访问v0；v0此时已在函数栈中
找v0的第一个为未访问的边；
找到就递归调用边指向的邻接点v1

访问邻接点v1；邻接点v1此时已在函数栈中
找v1的第一个为未访问的边；
找到就递归调用边指向的邻接点v2
没有找到就结束递归，v2出栈

回溯访问v0；v0此时还在函数栈中
找v0的第一个为未访问的边；（此时指向v1的边已经访问了）
找到就递归调用边指向的邻接点v3

提取栈顶v0；找v0的第一个未访问的边；
找到了；访问边指向的邻接点v1并入栈


新开通了本人的公众号，欢迎关注：燕南路GISer ，专注GIS干货分享，不定期更新。
主要兴趣：GIS、时空数据挖掘、python、机器学习深度学习
提问、求资源等都可在公众号后台留言
CSDN的部分内容会重写再搬迁到公众号，欢迎关注！

自己一边写的测试用的，所有的代码都经过了测试，还包括了一个模板类的栈，因为只是为了这个测试写的栈类，所以写的并不完整，不过也可以参考下。编译环境VS2005,C++.

干脆把stdafx.h也贴上来，给你拷过去直接用 


// stdafx.h : 标准系统包含文件的包含文件，
// 或是经常使用但不常更改的
// 特定于项目的包含文件
//

 

 stdafx.cpp就不拿过来了，都米动过

我要回帖

更多关于 折半查找非递归 的文章

 

随机推荐