如何将递归转换为非递归 - coderkian

标签: 递归 递归 coderkian | 发表时间:2014-05-28 23:20 | 作者:coderkian
出处:

递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率。

函数调用时,需要在栈中分配新的帧,将返回地址,调用参数和局部变量入栈。所以递归调用越深,占用的栈空间越多。如果层数过深,肯定会导致栈溢出,这也是消除递归的必要性之一。递归函数又可以分为尾递归和非尾递归函数,前者往往具有很好的优化效率,下面我们分别加以讨论。

尾递归函数

尾递归函数是指函数的最后一个动作是调用函数本身的递归函数,是递归的一种特殊情形。尾递归具有两个主要的特征:

  1. 调用自身函数(Self-called);

  2. 计算仅占用常量栈空间(Stack Space)。

为什么尾递归可以做到常量栈空间,我们用著名的fibonacci数列作为例子来说明。

fibonacci数列实现方法一般是这样的,

int FibonacciRecur(int n) {
if (0==n) return 0;
if (1==n) return 1;
return FibonacciRecur(n-1)+FibonacciRecur(n-2);
}

不过需要注意的是这种实现方法并不是尾递归,因为尾递归的最后一个动作必须是调用自身,这里最后的动作是加法运算,所以我们要修改一下,

int FibonacciTailRecur(int n, int acc1, int acc2) {
if (0==n) return acc1;
return FibonacciTailRecur(n-1, acc2, acc1+acc2);
}

好了,现在符合尾递归的定义了,用gcc分别加-O和-O2选项编译,下面是部分汇编代码,

-O2汇编代码

FibonacciTailRecur:
.LFB12:
testl %edi, %edi
movl %esi, %eax
movl %edx, %esi
je .L4
.p2align 4,,7
.L7:
leal (%rax,%rsi), %edx
decl %edi
movl %esi, %eax
testl %edi, %edi
movl %edx, %esi
jne .L7 // use jne
.L4:
rep ; ret

-O汇编代码

FibonacciTailRecur:
.LFB2:
pushq %rbp
.LCFI0:
movq %rsp, %rbp
.LCFI1:
subq $16, %rsp
.LCFI2:
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
cmpl $0, -4(%rbp)
jne .L2
movl -8(%rbp), %eax
movl %eax, -16(%rbp)
jmp .L1
.L2:
movl -12(%rbp), %eax
movl -8(%rbp), %edx
addl %eax, %edx
movl -12(%rbp), %esi
movl -4(%rbp), %edi
decl %edi
call FibonacciTailRecur //use call
movl %eax, -16(%rbp)
.L1:
movl -16(%rbp), %eax
leave
ret

可以看到-O2时用了jne命令,每次调用下层递归并没有申请新的栈空间,而是更新当前帧的局部数据,重复使用当前帧,所以不管有多少层尾递归调用都不会栈溢出,这也是使用尾递归的意义所在。

而-O使用的是call命令,这会申请新的栈空间,也就是说gcc默认状态下并没有优化尾递归,这么做的\的一个主要原因是有时候我们需要保留帧信息用于调试,而加-O2优化后,不管多少层尾递归调用,使用的都是第一层帧,是得不到当前帧的信息的,大家可以用gdb调试下就知道了。

除了尾递归,Fibonacci数列很容易推导出循环实现方式,

int fibonacciNonRecur(int n) {
int acc1 = 0, acc2 = 1;
for(int i=0; i<n; i++){
int t = acc1;
acc1 = acc2;
acc2 += t;
}
return acc1;
}

 在我的机器上,全部加-O2选项优化编译,运行时间如下(单位微秒)

n

fibonacciNonRecur

FibonacciTailRecur

FibonacciRecur

20

1

1

123

30

1

1

14144

将fibonacci函数的迭代,尾递归和递归函数性能比较,可以发现迭代和尾递归时间几乎一致,n的大小对迭代和尾递归运行时间影响很小,因为只是多执行O(n)条机器指令而已。但是n对递归函数影响非常大,这是由于递归需要频繁分配回收栈空间所致。正是由于尾递归的高效率,在一些语言如lua中就明确建议使用尾递归(参照《lua程序设计第二版》第6章)。

非尾递归函数

编译器无法自动优化一般的递归函数,不过通过模拟递归函数的过程,我们可以借助于栈将任何递归函数转换为迭代函数。直观点,递归的过程其实是编译器帮我们处理了压栈和出栈的操作,转换为迭代函数就需要手动地处理压栈和出栈。

下面我们以经典的快速排序为例子。

int partition(int *array, int low, int high) {
int val = array[low];
while(low < high) {
while(low<high && array[high]>=val) --high;
swap(&array[low], &array[high]);
while(low<high && array[low]<=val) ++low;
swap(&array[low], &array[high]);
}
return low;
}
void Quicksort(int *array, int b, int e) {
if (b >= e) return;
int p = partition(array, b, e);
Quicksort(array, b, p-1);
Quicksort(array, p+1, e);
}

其实不难看出快速排序的递归算法就是一个二叉树的先序遍历过程,先处理当前根节点,然后依次处理左子树和右子树。将快速排序递归算法转换为非递归相当于将二叉树先序遍历递归算法转为非递归算法。

二叉树先序遍历递归算法伪码

void PreorderRecursive(Bitree root){
if (root) {
visit(root);
PreorderRecursive(root->lchild);
PreorderRecursive(root->rchild);
}
}

二叉树先序遍历非递归伪码

void PreorderNonRecursive(Bitree root){
stack stk;
stk.push(root);
while(!stk.empty()){
p = stk.top();
visit(p);
stk.pop();
if(p.rchild) stk.push(stk.rchild);
if(p.lchild) stk.push(stk.lchild);
}
}

每次处理完当前节点后将右子树和左子树分别入栈,类似地,我们也很容易得到快速排序的非递归算法实现。partition将数组分为左右两部分,相当与处理当前节点,接下来要做的就是将左右子树入栈,那么左右子树需要保存什么信息呢?这个是处理非递归函数的关键,因为被调用函数信息需要压入栈中。快速排序只需要保存子数组的边界即可。

void QuicksortNonRecur(int *array, int b, int e) {
if (b >= e) return;
std::stack< std::pair<int, int> > stk;
stk.push(std::make_pair(b, e));
while(!stk.empty()) {
std::pair<int, int> pair = stk.top();
stk.pop();
if(pair.first >= pair.second) continue;
int p = partition(array, pair.first, pair.second);
if(p < pair.second) stk.push(std::make_pair(p+1, e));
if(p > pair.first) stk.push(std::make_pair(b, p-1));
}
}

 

总结

虽然将递归函数转换为迭代函数可以提高程序效率,但是转换后的迭代函数往往可读性差,难以理解,不易维护。所以只有在特殊情况下,比如对栈空间有严格要求的嵌入式系统,才需要转换递归函数。大部分情况下,递归并不会成为系统的性能瓶颈,一个代码简单易读的递归函数常常比迭代函数更易维护。

Reference:

https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/recursionConversion/page/recursionConversion.html

http://en.wikipedia.org/wiki/Tail_Recursion

http://c2.com/cgi/wiki?TailRecursion

http://c2.com/cgi/wiki?RecursionVsLoop




本文链接: 如何将递归转换为非递归,转载请注明。

相关 [递归 递归 coderkian] 推荐:

如何将递归转换为非递归 - coderkian

- - 博客园_首页
递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率. 函数调用时,需要在栈中分配新的帧,将返回地址,调用参数和局部变量入栈. 所以递归调用越深,占用的栈空间越多. 如果层数过深,肯定会导致栈溢出,这也是消除递归的必要性之一.

PHP正则之递归匹配

- KnightE - 风雪之隅
作者: Laruence(. 本文地址: http://www.laruence.com/2011/09/30/2179.html. 我记得早前有同事问, 正则是否能处理括号配对的正则匹配. 比如, 对于如下的待匹配的字符串:. 在以前, 这种情况, 正则无法处理, 最多只能处理固定层数的递归, 而无法处理无线递归的情况… 而在perl 5.6以后, 引入了一个新的特性: Recursive patterns, 使得这种需求可以被正确的处理..

递归算法与优化后的算法对比

- - 博客园_首页
前段时间看了《 【面试】——反应迟钝的递归》中的三个递归算法,斐波那契数列优化后的算法思路确实不错,但是后面2个数列用递归的话,个人感觉有点得不偿失. 能不用递归的话,尽量不用,因为有些算法完全可以用数学来解决. 因此,本文中将这三个数列的最终算法总结如下. 1、计算数组1,1,2,3,5,8,13...第30位的值.

使用递归唯一性验证的方式生成主键

- - CSDN博客数据库推荐文章
JadePool作为简化JDBC编程工具,提供 主键生成方法是必须的. 在JadePool中,ProcessVO用于事务型数据库的DML操作,Access用于非事务型数据库的DML操作,Access参照ProcessVO实现. 目前,JadePool只提供了单主键的键值生成方法,没有提供复合主键的生成方法.

SQLserver, Oracle 限制层数 递归查询和反向查询父记录

- - Oracle - 数据库 - ITeye博客
以前使用Oracle,觉得它的递归查询很好用,就研究了一下SqlServer,发现它也支持在Sql里递归查询. SqlServer2008版本的Sql如下:. 比如一个表,有id和pId字段,id是主键,pid表示它的上级节点,表结构和数据:. --下面的Sql是查询出1结点的所有子结点. select * from my1 --结果包含1这条记录,如果不想包含,可以在最后加上:where id <> 1.