递归计算向非递归计算转换模板

最近由于工作上的需要，研究了一下递归计算向非递归计算的转换问题。理论上而言，所有递归程序都可以用非递归程序来实现；这种理论的基础是递归程序的计算总能用一颗树型结构来表示。递归计算从求树根节点的值开始，树根节点的值依赖一个或多个子节点的值，子节点的值又依赖下一级子节点的值，如此直至树的叶子节点。叶子节点的值能直接计算出来，也就是递归程序的出口。如下图所示，是递归函数f(x) = f(x-1) + f(x-3), f(x) = 10 (x < 3)当x=4时的递归调用树。简单的递归计算，比如尾部递归，可以直接用循环来转换成非递归；对于复杂的递归，比如递归程序中递归调用点有多个，就是树型结构中一个父节点的值会依赖多个子节点的值，这种情形的递归转换成非递归通常需要借助堆栈加循环的方式。

 

直接用编程语言中的递归函数实现递归时，在时间和空间上都有可能造成浪费。从时间上来讲，如果递归调用点有多个，会由于中间计算结果没有被保存重用而导致大量的重复计算。比如递归函数f(x) = f(x-1) + f(x-3)，计算f(x)时，会先计算f(x-1)的值，在计算f(x-1)时会计算出许多子节点的值，这些值在计算f(x-3)时是可以重用的，但是当退出f(x-1)的调用后都被丢弃了，导致在计算f(x-3)时会重复很多计算。空间上，由于每次递归调用都要保留现场，递归变深时，树会迅速膨胀，占用的空间也会激增。

 

递归程序转换成非递归程序时有固定的模式可循，将这个模式抽象成通用的模板，就有可能实现递归至非递归程序的自动转换。根据前面的分析，将递归计算用树型结构来表达，计算父节点时，会要求计算出其子节点的值。如果用一个堆栈来表示，则计算父节点时，会先将该父节点压入堆栈，待到其依赖的所有子节点的值都计算出时，再将其弹出并计算其值；在计算其子节点时依照相同的原理，直至遇到叶子节点。考虑递归函数f(x) = f(x-1) + f(x-3), f(x) = 10 (x < 3)， x 的初始值为4，用如图所示的数据结构表示，往pre方向是堆栈的底部，往next的方向是堆栈的顶部，堆栈指针指向当前正在计算的节点。计算第一个子节点的堆栈情况如下所示：

 

计算f(4)时会先计算f(3)，计算f(3)时会先计算f(2)，f(2)=10，是叶子节点，那么f(3)的第一个子节点f(2)计算完成，开始计算f(3)的第二个节点f(0):

 

f(0)=10，至此f(3)的两个子节点都计算完成，可以求出f(3) = f(2) +f(0) = 20。f(3)求出后，相当于f(4)的第一个子节点被计算出来了，开始计算f(4)的第二个子节点的值f(1)：

 

f(1)=10，那么f(4)的两个子节点都已经被计算出来了，可以直接求f(4) = f(3) + f(1) = 30。由于此时已到堆栈底部，计算完成，弹出f(4)的计算结果，即为最终结果。

 

 

以上的示例虽然简单，但足以总结出如下规律：

结算某个节点的值时，有两种情况：

• 1) 该节点为叶子节点，可以直接求出其值；
• 2) 该节点为非叶子节点，需要先计算其依赖的子节点。该节点可能依赖多个子节点，子节点一个一个地计算，当最后一个子节点计算出来后，该节点的值可以顺利求出；
• 3) 在2)中计算子节点时，要么其子节点为叶子节点，进入1)，值能直接求出；否则，又进入2)计算下一级子节点。每个节点完成计算时都需要监测自己是不是父节点的最后一个子节点。如果是，就可以直接求父节点的值；如果非，就继续求下一个兄弟节点，即父节点的下一个子节点的值。

 

最后一条很关键，当每个节点完成计算时，它甚至没有信息可以判断前面哪个节点是其父节点！子节点没有父节点的信息，但父节点通过设置状态可以记录当前是在计算哪个子节点。对于特定的递归程序，每个父节点依赖的子节点的数目是确定的，就是递归调用点的数目；比如f(x) = f(x-1) + f(x-3)，递归调用点为2，可以确定每个父节点依赖2个子节点。

 

基于前面如图所示的堆栈结构，计算父节点时会依次计算其子节点，其子节点会依次紧跟在父节点之后压入堆栈。设每个节点的初始状态为0，计算完成后状态为3；则刚进入递归时树根节点的状态为0，此时把该节点当作父节点，开始计算其第一个子节点，父节点的状态设置成1，表示在计算它的第一个子节点。第一个子节点计算完成后，自身状态为3，回溯检查，发现前面的节点状态为1，可以确定其为父节点，并且仅计算出了第一个子节点的值，还需要计算第二个子节点的值。这时将该父节点的状态设置成2，表示在计算它的第二个子节点。第二个子节点计算完成自身状态变为3后，回溯检查，至第一个子节点，第一个子节点状态为3，再回溯，至状态为2的父节点，由于该父节点总共只有两个依赖的子节点，所以可以断定该父节点的最后一个子节点已经完成了计算，可以计算该父节点的值了。根据前面的数据结构可知该父节点的两个子节点依次紧跟其后，可以直接依次取出计算父节点的值。当该父节点完成计算后，状态变为3，这个时候就该回溯去寻找该父节点的父节点了。当最后一个父节点找到并完成计算后，递归计算就完成了。如上所示的堆栈中保存的是递归参数的值，在实际程序中，我们还需要空间来保存递归参数对应的计算出来的值，一般一个HashMap就足够了。

 

经过上面的分析，应该能很容易地将例子中的递归程序转换成非递归程序。今天有点累了，明天会附上用java实现的非递归程序。我们可以清楚的从代码中看出既定的规律，进而归纳出一个通用的递归向非递归程序转换的模板。

 

 

评论

10 楼 night_stalker 2009-03-04  

递归修改成迭代是不错的教材。

可是没很大实用性，因为瓶颈是递归算法的情况不很多，我们还可以把包含很多局部变量的代码段抽出成函数，还可以增加栈空间。

当然模版化的修改方法也不错，让机器完成这类工作，就更加不需要手动把递归改成非递归了。

建议不用在这种问题上纠结，因为太机械，这两算法本质上没什么区别。

像lisp就没有迭代，只有递归~~

如果你的算法会造成递归栈溢出，改成非递归以后很可能也会堆溢出-_-。




ps1：

递归与迭代的区别，其实是差分方程反向和正向递推的区别，也是归纳和演绎的区别。


ps2：

一些不需要栈就能改写的例子：

如f(n) = f(n-1) + f(n-2)

从n开始算就是递归，从2开始算就是迭代，这种转化连栈都不需要。


又如f(n) = f(n/2) + f(n/4)

我们可以设g(n) = g(n-1)/2

f*g(n) = f*g(n-1) + f*g(n-2)

设f' = f*g，则f = f'* g^-1

f'(n) = f'(n-1) + f'(n-2)

同样也不需要栈。


如果f(x)满足： 对任意a, f(a)==f(a)，

那么我们可以：写出对应的差分方程，求出差分方程的通解，将f改写成通解。

这样也不需要栈。


一些递归可以在编译期完成，c++的expression template，

这样运行时也不需要栈。

9 楼 sdh5724 2009-03-04  

递归有在简单的情况下， 是无可替代的。

不知道在大家有见过栈溢出的问题么， 如果一个太深递归， 会导致栈溢出， 线程栈虽然可以定义大小， 但是， 一个超过500线程的系统， 栈会消耗的太多的内存， 导致性能下降， 这个对JAVA有兴趣的朋友可以测试下， -Xss256k -Xss1024k 这样的性能差别。

如果对应用的可靠性要求很高，递归又很深度， 递归转非递归是程序员必要的技能。 任何东西都有他的适用价值， 纯粹的价值意义不大。

自己实现转非递归最简单办法就是实现自己的栈。 因为递归执行就是在栈上完成的。把握了这个， 就不难了。 当然特定的问题还有特定解决办法。 比如循环等操作。

8 楼 mathgl 2009-03-03  

除了 tail recursive 那种。其它类型的recursive改写都需要 手动 操作stack。貌似价值不大。写出来的程序也未必可读性很好。

7 楼 night_stalker 2009-03-03  

可惜啊，lz，尾递归在很早很早的时候就可以解析成迭代了

而且递归有一个好处——很容易修改成并行计算

6 楼 hfutxrg 2009-03-03  

<div class="quote_title">mingliangfeng 写道</div>
<div class="quote_div">
<p>最近由于工作上的需要，研究了一下递归计算向非递归计算的转换问题。理论上而言，所有递归程序都可以用非递归程序来实现；这种理论的基础是递归程序的计算总能用一颗树型结构来表示。递归计算从求树根节点的值开始，树根节点的值依赖一个或多个子节点的值，子节点的值又依赖下一级子节点的值，如此直至树的叶子节点。叶子节点的值能直接计算出来，也就是递归程序的出口。如下图所示，是递归函数f(x) = f(x-1) + f(x-3), f(x) = 10 (x &lt; 3)当x=4时的递归调用树。简单的递归计算，比如尾部递归，可以直接用循环来转换成非递归；对于复杂的递归，比如递归程序中递归调用点有多个，就是树型结构中一个父节点的值会依赖多个子节点的值，这种情形的递归转换成非递归通常需要借助堆栈加循环的方式。</p>
<p> <img src="/upload/attachment/26811/2e38a4e7-71b6-3be0-9c2d-4c242f2284c2.png" height="204" alt="" width="471" /></p>
<p>直接用编程语言中的递归函数实现递归时，在时间和空间上都有可能造成浪费。从时间上来讲，如果递归调用点有多个，会由于中间计算结果没有被保存重用而导致大量的重复计算。比如递归函数f(x) = f(x-1) + f(x-3)，计算f(x)时，会先计算f(x-1)的值，在计算f(x-1)时会计算出许多子节点的值，这些值在计算f(x-3)时是可以重用的，但是当退出f(x-1)的调用后都被丢弃了，导致在计算f(x-3)时会重复很多计算。空间上，由于每次递归调用都要保留现场，递归变深时，树会迅速膨胀，占用的空间也会激增。</p>
<p> </p>
<p>递归程序转换成非递归程序时有固定的模式可循，将这个模式抽象成通用的模板，就有可能实现递归至非递归程序的自动转换。根据前面的分析，将递归计算用树型结构来表达，计算父节点时，会要求计算出其子节点的值。如果用一个堆栈来表示，则计算父节点时，会先将该父节点压入堆栈，待到其依赖的所有子节点的值都计算出时，再将其弹出并计算其值；在计算其子节点时依照相同的原理，直至遇到叶子节点。考虑递归函数f(x) = f(x-1) + f(x-3), f(x) = 10 (x &lt; 3)， x 的初始值为4，用如图所示的数据结构表示，往pre方向是堆栈的底部，往next的方向是堆栈的顶部，堆栈指针指向当前正在计算的节点。计算第一个子节点的堆栈情况如下所示：</p>
<p> <img src="/forums/43/topics/upload/attachment/26665/96f0ca8c-1957-3c12-b9d4-650ba04d6f8a.png" height="86" alt="" width="409" /></p>
<p>计算f(4)时会先计算f(3)，计算f(3)时会先计算f(2)，f(2)=10，是叶子节点，那么f(3)的第一个子节点f(2)计算完成，开始计算f(3)的第二个节点f(0):</p>
<p> <img src="/forums/43/topics/upload/attachment/26667/6590ca99-ad63-3310-bb0c-ebaa0037aaf6.png" height="85" alt="" width="409" /></p>
<p>f(0)=10，至此f(3)的两个子节点都计算完成，可以求出f(3) = f(2) +f(0) = 20。f(3)求出后，相当于f(4)的第一个子节点被计算出来了，开始计算f(4)的第二个子节点的值f(1)：</p>
<p> <img src="/forums/43/topics/upload/attachment/26671/066b6d3c-f8e8-31e6-a86d-f97c1c06cada.png" height="84" alt="" width="409" /></p>
<p>f(1)=10，那么f(4)的两个子节点都已经被计算出来了，可以直接求f(4) = f(3) + f(1) = 30。由于此时已到堆栈底部，计算完成，弹出f(4)的计算结果，即为最终结果。</p>
<p> <img src="/forums/43/topics/upload/attachment/26815/80e60afb-8ee9-3587-9a67-e0f5c17ea02d.png" height="84" alt="" width="409" /></p>
<p> </p>
<p>以上的示例虽然简单，但足以总结出如下规律：</p>
<p>结算某个节点的值时，有两种情况：</p>
<ul>
<li>1) 该节点为叶子节点，可以直接求出其值；</li>
<li>2) 该节点为非叶子节点，需要先计算其依赖的子节点。该节点可能依赖多个子节点，子节点一个一个地计算，当最后一个子节点计算出来后，该节点的值可以顺利求出；</li>
<li>3) 在2)中计算子节点时，要么其子节点为叶子节点，进入1)，值能直接求出；否则，又进入2)计算下一级子节点。每个节点完成计算时都需要监测自己是不是父节点的最后一个子节点。如果是，就可以直接求父节点的值；如果非，就继续求下一个兄弟节点，即父节点的下一个子节点的值。</li>
</ul>
<p> </p>
<p>最后一条很关键，当每个节点完成计算时，它甚至没有信息可以判断前面哪个节点是其父节点！子节点没有父节点的信息，但父节点通过设置状态可以记录当前是在计算哪个子节点。对于特定的递归程序，每个父节点依赖的子节点的数目是确定的，就是递归调用点的数目；比如f(x) = f(x-1) + f(x-3)，递归调用点为2，可以确定每个父节点依赖2个子节点。</p>
<p> </p>
<p>基于前面如图所示的堆栈结构，计算父节点时会依次计算其子节点，其子节点会依次紧跟在父节点之后压入堆栈。设每个节点的初始状态为0，计算完成后状态为3；则刚进入递归时树根节点的状态为0，此时把该节点当作父节点，开始计算其第一个子节点，父节点的状态设置成1，表示在计算它的第一个子节点。第一个子节点计算完成后，自身状态为3，回溯检查，发现前面的节点状态为1，可以确定其为父节点，并且仅计算出了第一个子节点的值，还需要计算第二个子节点的值。这时将该父节点的状态设置成2，表示在计算它的第二个子节点。第二个子节点计算完成自身状态变为3后，回溯检查，至第一个子节点，第一个子节点状态为3，再回溯，至状态为2的父节点，由于该父节点总共只有两个依赖的子节点，所以可以断定该父节点的最后一个子节点已经完成了计算，可以计算该父节点的值了。根据前面的数据结构可知该父节点的两个子节点依次紧跟其后，可以直接依次取出计算父节点的值。当该父节点完成计算后，状态变为3，这个时候就该回溯去寻找该父节点的父节点了。当最后一个父节点找到并完成计算后，递归计算就完成了。如上所示的堆栈中保存的是递归参数的值，在实际程序中，我们还需要空间来保存递归参数对应的计算出来的值，一般一个HashMap就足够了。</p>
<p> </p>
<p>经过上面的分析，应该能很容易地将例子中的递归程序转换成非递归程序。今天有点累了，明天会附上用java实现的非递归程序。我们可以清楚的从代码中看出既定的规律，进而归纳出一个通用的递归向非递归程序转换的模板。</p>
<p> </p>
<p> </p>
</div>
<p> </p>

5 楼 run_xiao 2008-08-06  

lindily 写道

递归转非递归一般的目的是，减少计算复杂度，例如如消除重复计算
你的这个f(x)，x=6时，f(6)f(5)f(4)f(1)各计算一次，f(3)计算两次，f(2)计算三次，f(0)计算两次，这里有很多重复的调用

  

4 楼 javaeyebird 2008-08-01  

lindily 写道

回楼上，你怎么知道“用非递归实现的算法在时间和空间上不一定比递归好”？
递归算法如果用汇编的看法来看，就是不断地进行中断、保存现场、跳转，直到依次回调，恢复现场。这中间消耗大量CPU和内存（主要是堆栈）资源，而且代码效率不一定很高，而转为非递归，虽然代码量上去了，但是由于采用了简单的逻辑，运算效率要高

递归用不着中断，保存现场是因为寄存器不够用
自己用代码实现栈，同样涉及到数据访问的调度，寄存器一样不够用，也要“保存”、“恢复”
cpu提供的栈操作效率一般都比自己用代码实现的栈来得高
所以，通常只在进程（或线程）申请的栈区不够用时，才自己在堆上实现栈

递归转非递归一般的目的是，减少计算复杂度，例如如消除重复计算
你的这个f(x)，x=6时，f(6)f(5)f(4)f(1)各计算一次，f(3)计算两次，f(2)计算三次，f(0)计算两次，这里有很多重复的调用

如果仍用递归，一种优化方式是：先创建一个整数数组s，长度和x+1相同，初始0
if x<3 then f(x)=10
else if s[x]>0 then f(x)=s[x]
else f(x)=s[x]=f(x-1)+f(x-3)
这样每个x都只会计算一次，计算复杂度由O(2的x方)降到O(x)
对于很大的x值，能极大地提高效率

这个方法的关键一点就是函数必须是幂等的
而许多递归并非这样，比如图论中的一些操作，需要修改节点做些标记，这样的函数就不能直接使用这个方法

进一步优化，就可以改成递推，同样有个数组s，然后从小往大的逐个计算：
s[0]=s[1]=s[2]=10
for (y from 3 to x)
  s[y] = s[y-1] + s[y-3]
最后s[x]就是f(x)
这样时间复杂度仍然是O(x)，但系数比上面的优化小一点，效率也高一点
（如果再做进一步优化，这个数组只要放3个数就够了，空间复杂度也优化成O(1)常量）
这个递推和原始的那个递归相比，实现的思路很不同

对于各种递归，因为存在非幂等的函数，没有单一的规律来做这样的 能优化时间复杂度的 转换
而对于大量重复的幂等计算，直接在函数里判断并保存计算过的值，也不需要特意把递归改成递推，这也是缓存的一般做法，比自己用代码实现栈，然后缓存值，更简单实用

3 楼 lindily 2008-06-15  

回楼上，你怎么知道“用非递归实现的算法在时间和空间上不一定比递归好”？
递归算法如果用汇编的看法来看，就是不断地进行中断、保存现场、跳转，直到依次回调，恢复现场。这中间消耗大量CPU和内存（主要是堆栈）资源，而且代码效率不一定很高，而转为非递归，虽然代码量上去了，但是由于采用了简单的逻辑，运算效率要高

2 楼 karidyang 2008-06-12  

问题是，用非递归实现的算法在时间和空间上不一定比递归好。递归调用的运行时堆栈来保存每次递归前的信息，理论上用人工控制的一个栈加上一些代码就能实现递归算法。

1 楼 seen 2008-06-07  

有点意思 stay tune for next scene...