求助一个用堆栈来模拟fibr递归函数实现

feiyang21687

利用一个堆栈来模拟递归函数的实现，以fibr函数为例。
要求效率比递归实现高，空间使用率尽量的高，不知道各位大侠有什么好的点子？在下愿闻赐教

feiyang21687

我自己顶，希望大家来谈谈自己的想法。

feiyang21687

来个具体的吧，对于这个递归函数用堆栈来模拟：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

更正上面的式子，原本的式子是要计算f( more(n/2) ) + f( less(n/2) ) + n，其中more(n/2)表示不大于n/2的最大的整数，less(n/2)表示大于n/2最小的整数，上面的描述有误，不好意思。大家来讨论一下思路。

feiyang21687

怎么没有人啊？自己顶

tyc611

>> 来个具体的吧，对于这个递归函数用堆栈来模拟：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

如果是上面那个意思的话，由递推公式：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[i] = f[i/2] + f[i/2 + 1] + i;

int fn = f[n/2] + f[n/2 + 1] + n;

空间需要 n/2 + 1 + 1 个数组元素（下标为0的数组元素没用），时间上比递归节约了很多，因为用表保存了中间结果，避免了不少重复计算

另外，我并没有直接把递归转换成栈实现，方法是可行的，但是这种转换方法比较难懂，如果需要自己可以查找资料，讲算法的书上有些有

[[i] 本帖最后由 tyc611 于 2007-2-3 23:17 编辑 [/i]]

feiyang21687

忘记了，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

>> 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

如下是模拟栈的递归实现（如果学过编译原理就不难理解）
fibr函数是C递归代码，main中的是模拟递归代码

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. #define ALEN(v) (sizeof(v)/sizeof((v)[0]))
   
6. 
   
7. int fibr(int n){
   
8.         printf("%d ", n);
   
9.         return n<=1?1:fibr(n/2)+fibr((n+1)/2)+n;
   
10. }
    
11. 
    
12. int ip;
    
13. int ax;
    
14. int bp;
    
15. int ss[100];
    
16. int sp = ALEN(ss);
    
17. 
    
18. void push(int n){
    
19.         if(--sp<0){
    
20.                 sp=ALEN(ss)-1;
    
21.                 printf("\nStack Overflow!!\n");
    
22.                 exit(-1);
    
23.         }
    
24.         ss[sp]=n;
    
25. }
    
26. 
    
27. int pop(void){
    
28.         if(sp>=ALEN(ss)){
    
29.                 sp=0;
    
30.                 printf("\nStack Overflow!!\n");
    
31.                 exit(-1);
    
32.         }
    
33.         return ss[sp++];
    
34. }
    
35. 
    
36. void call(void){
    
37.         push(ip+1);
    
38.         ip=0;
    
39. }
    
40. 
    
41. void ret(void){
    
42.         ip = pop();
    
43. }
    
44. 
    
45. int main(void){
    
46.         printf("= %d\n", fibr(7));
    
47.         push(7);
    
48.         ip=-2;
    
49.         call();
    
50.         while(ip>=0){
    
51.                 switch(ip){
    
52.                 case 0:
    
53.                         push(bp);
    
54.                         bp=sp;
    
55.                         printf("%d ", ss[bp+2]);
    
56.                         if(ss[bp+2]<=1){
    
57.                                 ax=1;
    
58.                                 ip=4;
    
59.                         }else{
    
60.                                 ip=1;
    
61.                         }
    
62.                         break;
    
63.                 case 1:
    
64.                         push(ss[bp+2]/2);
    
65.                         call();
    
66.                         break;
    
67.                 case 2:
    
68.                         sp+=1;
    
69.                         push(ax);
    
70.                         push((ss[bp+2]+1)/2);
    
71.                         call();
    
72.                         break;
    
73.                 case 3:
    
74.                         sp+=1;
    
75.                         ax+=pop()+ss[bp+2];
    
76.                         ip=4;
    
77.                         break;
    
78.                 case 4:
    
79.                         bp=pop();
    
80.                         ret();
    
81.                         break;
    
82.                 }
    
83.         }
    
84.         sp+=1;
    
85.         printf("= %d\n", ax);
    
86.         return 0;
    
87. }
    

复制代码