利用一个堆栈来模拟递归函数的实现，以fibr函数为例。
要求效率比递归实现高，空间使用率尽量的高，不知道各位大侠有什么好的点子？在下愿闻赐教
feiyang21687 回复于：2007-02-02 22:18:03
我自己顶，希望大家来谈谈自己的想法。
feiyang21687 回复于：2007-02-03 01:24:03
来个具体的吧，对于这个递归函数用堆栈来模拟：f(n) = f(n/2) + f(n/2 +1) + n
堆栈里面的数据结构应该是这样的（设n=7)：7,3,1,2,1,1,4,2,1,1,2,1,1。就是一个二叉树，不过不知道怎么写代码可以高效的实现这种入栈。
feiyang21687 回复于：2007-02-03 01:38:12
更正上面的式子，原本的式子是要计算f( more(n/2) ) + f( less(n/2) ) + n，其中more(n/2)表示不大于n/2的最大的整数，less(n/2)表示大于n/2最小的整数，上面的描述有误，不好意思。大家来讨论一下思路。
feiyang21687 回复于：2007-02-03 22:19:16
怎么没有人啊？自己顶
tyc611 回复于：2007-02-03 23:03:10
>> 来个具体的吧，对于这个递归函数用堆栈来模拟：f(n) = f(n/2) + f(n/2 +1) + n
>> 更正上面的式子，原本的式子是要计算f( more(n/2) ) + f( less(n/2) ) + n，其中more(n/2)表示不大于n/2的最大的整数，less(n/2)表示大于n/2最小的整数，上面的描述有误，不好意思。
我觉得，根据你下面的描述，上面的递归公式没错啊
tyc611 回复于：2007-02-03 23:14:47
如果是上面那个意思的话，由递推公式：f(n) = f(n/2) + f(n/2 +1) + n
可知，f(2) = f(1) + f(2) + 2，无限递归了，所以应该给f(1)和f(2)赋初值
然后可以按下面的方法直接递推计算：
int f[NUM];
f[1] = some_value;
f[2] = some_value;
for (int i = 3; i <= n/2 + 1; ++i)
f = f[i/2] + f[i/2 + 1] + i;
int fn = f[n/2] + f[n/2 + 1] + n;
空间需要 n/2 + 1 + 1 个数组元素（下标为0的数组元素没用），时间上比递归节约了很多，因为用表保存了中间结果，避免了不少重复计算
另外，我并没有直接把递归转换成栈实现，方法是可行的，但是这种转换方法比较难懂，如果需要自己可以查找资料，讲算法的书上有些有
[ 本帖最后由 tyc611 于 2007-2-3 23:17 编辑 ]
feiyang21687 回复于：2007-02-03 23:34:44
忘记了，f(1) = 1。
对于你说的：
引用：原帖由 tyc611 于 2007-2-3 23:14 发表
如果是上面那个意思的话，由递推公式：f(n) = f(n/2) + f(n/2 +1) + n
可知，f(2) = f(1) + f(2) + 2，无限递归了，所以应该给f(1)和f(2)赋初值
然后可以按下面的方法直接递推计算：
int f[NUM];
f[1] = some ...
这个是用迭代的方法。不过我想用堆栈来模拟一下递归的过程。现在关键的问题没有好方法来实现：（7,3,1,2,1,1,4,2,1,1,2,1,1）这种进栈顺序。不知道老大有没有好的方法？
tyc611 回复于：2007-02-03 23:54:02
>> 7,3,1,2,1,1,4,2,1,1,2,1,1
这个是怎么得来的？
如果是一个返回点还好转换一点，有两个点转换起来比较麻烦，但是有一种模式可套用，我也说不清楚，建议找资料看吧
可以看看这本书，下面的链接能免费试读，在45页有讲递归转非递归的栈实现方法（需要下载阅读器）
http://www.china-pub.com/computers/common/info.asp?id=11749
[ 本帖最后由 tyc611 于 2007-2-3 23:55 编辑 ]
cobras 回复于：2007-02-04 11:13:12
如下是模拟栈的递归实现（如果学过编译原理就不难理解）
fibr函数是C递归代码，main中的是模拟递归代码
#include <stdio.h>
#include <stdlib.h>
#define ALEN(v) (sizeof(v)/sizeof((v)[0]))
int fibr(int n){
printf("%d ", n);
return n<=1?1:fibr(n/2)+fibr((n+1)/2)+n;
}
int ip;
int ax;
int bp;
int ss[100];
int sp = ALEN(ss);
void push(int n){
if(--sp<0){
sp=ALEN(ss)-1;
printf("\nStack Overflow!!\n");
exit(-1);
}
ss[sp]=n;
}
int pop(void){
if(sp>=ALEN(ss)){
sp=0;
printf("\nStack Overflow!!\n");
exit(-1);
}
return ss[sp++];
}
void call(void){
push(ip+1);
ip=0;
}
void ret(void){
ip = pop();
}
int main(void){
printf("= %d\n", fibr(7));
push(7);
ip=-2;
call();
while(ip>=0){
switch(ip){
case 0:
push(bp);
bp=sp;
printf("%d ", ss[bp+2]);
if(ss[bp+2]<=1){
ax=1;
ip=4;
}else{
ip=1;
}
break;
case 1:
push(ss[bp+2]/2);
call();
break;
case 2:
sp+=1;
push(ax);
push((ss[bp+2]+1)/2);
call();
break;
case 3:
sp+=1;
ax+=pop()+ss[bp+2];
ip=4;
break;
case 4:
bp=pop();
ret();
break;
}
}
sp+=1;
printf("= %d\n", ax);
return 0;
}
feiyang21687 回复于：2007-02-04 11:15:44
引用：>> 7,3,1,2,1,1,4,2,1,1,2,1,1
这个是怎么得来的？
这个序列就是递归调用时候堆栈里面的存储数据的顺序，我是通过把递归式展开得到的这个序列。这个序列可以用一棵二叉树来描述。
PS.你也是北邮的吗？
cobras 回复于：2007-02-04 11:18:46
修正LZ递推式f(n)=f(n/2)+f((n+1)/2)+n,f(1)=1
tyc611 回复于：2007-02-04 11:54:17
引用：原帖由 cobras 于 2007-2-4 11:18 发表
修正LZ递推式f(n)=f(n/2)+f((n+1)/2)+n,f(1)=1
楼主的递推式是正确的
引用：
原本的式子是要计算f( more(n/2) ) + f( less(n/2) ) + n，其中more(n/2)表示不大于n/2的最大的整数，less(n/2)表示大于n/2最小的整数
例如：
当 n = 2 时，more(n/2) = more(2/2) = 1, less(n/2) = less(2/2) = 2，所以 f(2) = f(1) + f(2) + 2 （无限递归）
而你的递推式有：f(2) = f(1) + f(1) + 2，所以你的是不正确
（注意：上面递推式中n/2作了向下取整计算）
另外，按照楼主的要求，必须给定 f(1) 和 f(2) 的初值才行
引用：more(n/2) <= n/2 <less(n/2)，more和less相差1
tyc611 回复于：2007-02-04 11:56:01
引用：原帖由 feiyang21687 于 2007-2-4 11:15 发表
这个序列就是递归调用时候堆栈里面的存储数据的顺序，我是通过把递归式展开得到的这个序列。这个序列可以用一棵二叉树来描述。
PS.你也是北邮的吗？
不知道你是按哪个公式展开的，我展开结果不是这样的
PS：不是的^_^
cobras 回复于：2007-02-04 11:58:57
用我的递推式才可得到楼主需要的序列
tyc611 回复于：2007-02-04 12:21:12
引用：原帖由 cobras 于 2007-2-4 11:13 发表
如下是模拟栈的递归实现（如果学过编译原理就不难理解）
fibr函数是C递归代码，main中的是模拟递归代码
#include <stdio.h>
#include <stdlib.h>
#define ALEN(v) (sizeof(v)/sizeof(( ...
很不错，赞一个
引用：
用我的递推式才可得到楼主需要的序列
恩，不过，就怕他序列推错了，呵呵
upstorm 回复于：2007-02-04 16:06:05
引用：原帖由 cobras 于 2007-2-4 11:13 发表
如下是模拟栈的递归实现（如果学过编译原理就不难理解）
fibr函数是C递归代码，main中的是模拟递归代码
#include <stdio.h>
#include <stdlib.h>
#define ALEN(v) (sizeof(v)/sizeof(( ...
强:D
如果按楼主所说的，要求效率高，空间利用率高，这不是摆明了要再去增加一个寄存器吗？
feiyang21687 回复于：2007-02-05 00:07:17
引用：
while(ip>=0){
switch(ip){
case 0:
push(bp);
bp=sp;
printf("%d ", ss[bp+2]);
if(ss[bp+2]<=1){
ax=1;
ip=4;
}else{
ip=1;
}
break;
case 1:
push(ss[bp+2]/2);
call();
break;
case 2:
sp+=1;
push(ax);
push((ss[bp+2]+1)/2);
call();
break;
case 3:
sp+=1;
ax+=pop()+ss[bp+2];
ip=4;
break;
case 4:
bp=pop();
ret();
break;
}
}
[size=3]小弟愚笨，这段代码不甚明白，是否可以说明一下。多谢了。[/size]
|
