一个较奇特的递归程序 wxh zt

wxhwhmanshan

一个较奇特的递归程序解析fun(int n,int *s)        
{ int f1,f2;        
  if(n==1||n==2)*s=1;      
  else      
{      
  fun(n-1,&f1);      
  fun(n-2,&f2);      
  *s=f1+f2;      
}      
}        
main()        
{int x;        
fun(6,&x);        
printf("%d\n",x);        
getch();      
}        

这是群中某朋友发的程序，要我帮着剖析原理，说实话，自己也是第一次见到这种形式的递归，我把它命名为“双重递归”吧。因为本人天资愚钝的缘故，所以花了较长时间去分析并尽最大努力将它表述出来。  
我们先来看看该函数的递归次数      
fun(6,&x);      
在传入形参中，其中出现了“双重递归”      
即：fun(n-1,&f1);        
    fun(n-2,&f2);        

先n=6从主调函数传入，即      
fun(5,&f1)+fun(4,&f2)等于最终递归完毕的结果（其实更准确的说法应该是递归最外层的f1+f2的值）      

分析f1(中的值的递归变化)      
fun(5,&f1)=fun(4,&f1)+fun(3,&f2)        
fun(4,&f1)=fun(3,&f1)+fun(2,&f2)      
fun(3,&f1)=fun(2,&f1)+fun(1,&f2)      
fun(2,&f1)=1      

分析f2(中的值的递归变化)      
fun(4,&f2)=fun(3,&f1)+fun(2,&f2)      
fun(2,&f2)=1      

现在我们来回推      
回推f1(中的值的递归变化)      
fun(2,&f1)=1      

fun(3,&f1)=fun(2,&f1)+fun(1,&f2)      
fun(3,&f1)=1+1      

fun(4,&f1)=fun(3,&f1)+fun(2,&f2)      
fun(4,&f1)=2+1      

fun(5,&f1)=fun(4,&f1)+fun(3,&f2)      
fun(5,&f1)=3+(1+1)      

回推f2(中的值的递归变化)      
fun(2,&f2)=1      
fun(4,&f2)=fun(3,&f1)+fun(2,&f2)      
fun(4,&f2)=(1+1)+1      

所以，fun(5,&f1)+fun(4,&f2)的最终结果是(3+(1+1))+((1+1)+1)=8      

<递归结束 返回主调函数>      
*s指向的是实参的x，所以printf("%d\n",x); 输出结果为8      

hdm2968

很难研究，究竟楼主是个怎样的人？除了转贴或灌水之外，根本没说过其他多余的话，可能是怀才不遇吧
http://bbs.gameres.com/showthread.asp?threadid=9881

flyv

1 1 2 3 5 8 13 21 ...

flyv

1 1 2 3 5 8 13 21 34 55 89....
1 2 3 4 5 6 7   8  9   10 11....

楼主没学过递归吧？

hdm2968

这个楼主发的绝大多数是转贴的，用途估计是收藏或者灌水

mbysky

简单的二叉数递归遍历就是需要在函数里调两次递归的，这个好像也没什么特别的，LZ能说说高深的用处吗？

flyv

如果是传入的指针在运行过程中再作为参数传入递归的，可能就是……很可怕的结果

航天奇侠

我怎么感觉有问题。
递归不知道是谁发明的，说什么好理解，优美。我只觉得头疼。