递归与非递归的比较
-
递归与非递归的比较
非递归效率高；递归代码写出来思路清晰，可读性强。
生成可执行文件大小应该和编译器有关吧。。。。
递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。
以二叉树搜索为例：
bool search(btree* p, int v)
{
if (null == p)
return false;
if (v == p->v)
return true
else
{
if (v <
p->v)
return search(p->left, v);
else
return
search(p->right, v);
}
}
如果这个二叉树很庞大，反复递归函数调用开销就很大，万一
堆栈溢出怎么办？
现在我们用循环改写：
bool search(btree* p, int v)
{
while (p)
{
if (v == p->v)
return true;
else
{
if (v <
p->v)
p = p->left;
else
p = p->right;
}
}
return false;
}
--------------------------
--------------------------------------------------
-----------------------------
递归好处：
代码更简洁清晰，可读性更好
递归可读性好这一点，
对于初学者可能会反对。
实际
上递归的代码更清晰，
但是从学习的角
度要理解递归真正发生的
什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，
可能是不容易。
但是不可否认递归的代码更简洁。
一般来说，
一个人可能很容易的写出前中
后序的二叉树遍历的递归算法，
要
写出相应的非递归算法就比较考验水平了，
恐怕至少一半
的人搞
不定。所以说递归代码更简洁明了。
递归坏处：
由于递归需要系统堆栈，
所以空间消耗要比非递归代码要大很多。
而且，
如
果递归深度太大，可能系统撑不住。
楼上的有人说：
小的简单的用循环
,,
太复杂了就
递归吧
,,
免得循环看不懂
话虽然简单，
其实非常有道理：
对于小东西，
能用循环干嘛要折腾？
如果比较复杂，
在
系统撑的住的情况下，写
递归有利于代码的维护（可读性好）
另：
一般尾递归
（即最后一句话进行递归）
< br>和单向递归
（函数中只有一个递归调用地方）
都可以用循
环来避免递归，
更复杂的情况则要引入栈来进行压栈出栈来改造成非递归，
这个
栈不一定要严格引入栈数据结构，只需要有这样的思路，用数组什么的就
可以。
至于教科书上喜欢
n!
的示例，
我想只是便于递归思路的引进和建立。
真正做代码不可能的。
---------------
--------------------------------------------------
--------------------------------------------------
-
循环方法比递归方法快
,
因为循
环避免了一系列函数调用和返回中所涉及到的参数传
递和返回值的额外开销。
递归和循环之间的选择。一般情况下
,
当循环方法比较容易找到时
,
你应该
避免使用递
归。这在问题可以按照一个递推关系式来描述时
,
是时常遇到的
,
比如阶乘问题就是这种情
况。
反过来
,
当很难建立一个循环方法时
,
递归就是很好的方法。实际上
,
在某些情形下
,
递归方法总是显而易见的
,
而循环方
法却相当难找到。
当某些问题的底层数据结构本身就是
递归时<
/p>
,
则递归也就是最好的方法了。
-----------------------------------------
--------------------------------------------------
---------------------------
递归其实是方便了程序员
难为了机器。
它只要得到数学公式就能很方便的写出程序。
优<
/p>
点就是易理解，容易编程。但递归是用栈机制实现的（
c++
），每深入一层，都要占去一块
栈数据区域，
对嵌套层数深的一些算法，
递归会力不从心，
空间上会以内存
崩溃而告终，
而
且递归也带来了大量的函数调用，
这也有许多额外的时间开销。
所以在深度大时，
它的
时空
性就不好了。
循环其缺点就是不容易理解，
编写复
杂问题时困难。
优点是效率高。
运行时间只因循环
次数增加而增加，没什么额外开销。空间上没有什么增加。
----------------------------------------------
--------------------------------------------------
----------------------
递归算法与迭代算法的设计思路区别
在于：
函数或算法是否具备收敛性，
当且仅当一个
算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。
当然，
从理论上说，
所有
的递归函数都可以转换为迭代函数，
反之亦然，
然而代价通常都
是
比较高的。
但从算法结构来说，
递归声明的结构
并不总能够转换为迭代结构，
原因在于结构的引申
本身属于递归
的概念，
用迭代的方法在设计初期根本无法实现，
这就像动多态
的东西并不总
是可以用静多态的方法实现一样。
这也是为什么在
结构设计时，
通常采用递归的方式而不是
采用迭代的方式的原因
，
一个极典型的例子类似于链表，
使用递归定义及其简单，
但对于内
存定义
(
数组方式
)
其定义及调用处理说明就变得很晦涩，尤其是在遇到
环链、图、网格等问
题时，使用迭代方式从描述到实现上都变得很不现实。
=================================
==============================================
随笔
- 22
文章
- 0
评论
- 0
把递归函数转换成非递归程序的一般方法
把递归算法转化为非递归算法有如下三种基本方法：
(1).
通过分析，跳过分解过程，直接用循环结构的算法实
现求解过程。
(2).
自己用栈模
拟系统的运行时栈，
通过分析只保存必须保存的信息，
从而用非
递归算法替
代递归算法。
(3).
利用栈保存参数，
由于栈的后进先出特性吻合递归算法的执行过
程，
因而可以用非递归
算法替代递归算法。
●
递归函数的原理
用栈保存未完成的工作，在适当的时候从栈中取出并执行。
系统保存了工作的数据和状态，数据就是函数的局部变量，
状态就是程序指针。
●
非递归程序原理
1.
和递归函数的原理相同，只不过是把由系统负责保存工作
信息变为程序自己保存，这样能减少保存数据的冗余
(
主要是
节省了局部变量的空间
)
，提高存储效率。
2.
把程序要完成的工作分成两类：手头工作和保存在栈中的
待完成的工作。手头工作指程序正在做的工作。由于某些工作
不能一步完成，必须暂缓完成，于是可把它保存在栈中，这就
是待完成的工作。
3.
手头工作必须有其结束条件，不能永远做下去；保存的
待完成工作必须含有完成该项工作的所有必要信息。
4.
程序必须有秩序地完成各项工作。如，可把手头工作恰当
处理（直接处理或暂时保存）后，才能继续接手下一步的工作。
5.
待完成工作必须转换成手头工作才能处理。
●
栈的大小
所有递归问题，其递归过程可以展开成一棵树，叶子节点是
可解的，按照问题的要求，处理所有叶子节点，就可解决
问题本身。可能需要保存
(Data, Status)
，
Data
是工作数据，
Status
是工作状态；（
Data,
Status
）决定了整个工作。
栈的大小等于树的高度
-1
，
-1
是因为根节点不需保存。
●
举例
例
1.
汉诺塔问题
递归函数：
void
Hanoi(UINT x, UINT y, UINT n)
// x
Source
// y
Destination
//
n
Number of plates
{
if (n == 0) return;
Hanoi(x, x^y, n-1);
Move(x, y);
Hanoi(x^y, y,
n-1);
}
说明：
x
、
y
可取
1
、
2
、
3
三数之一，并且
x≠y
，
x
^y
表示
x
、
y
按位异或，
得到除
x
、
y
之外的第三个数。<
/p>
1^2=3, 1^3=2, 2^3=1
非递归程序：
#define N
5
tyepdef struct _HANOIDATA
{
UINT x;
UINT y;
UINT n;
}HANOIDATA;
void Hanoi(HANOIDATA hanoiData)
{
HANOIDATA
stack[N];
int
top = -1;
// stack pointer
while
(hanoiData.n || top != -1)
//
存在手头工作或待完成工作
{
while (hanoiData.n)
//
处理手头工作直到无现成的手头工作，