递归算法

问题描述

编写如下定义的递归函数的递归算法

g(m,n)=0 当m=0,n>=0时，g(m,n)=g(m-1,2n)+n当m>0,n>=0时

代码

View Code

 1 View Code 
 2 #include<stdio.h>
 3 int fun(int m, int n)
 4 {
 5     
 6     if(m==0&&n>=0)
 7         return 0;
 8     else
 9       return fun(m-1,2*n)+n;//我的了个去，把2*n写成2n，我太不细心了，好好做。
10 }
11 
12 int main()
13 {
14   int m,n,s;
15   printf("请输入两个参数：");
16   scanf("%d,%d",&m,&n);
17   s=fun(m,n);
18   printf("%d\n",s);
19   return 0;
20 }

问题描述：

写出求递归函数F(n)的递归算法，并消除递归：

F(n)=n+1 当n=0;F(n)=n*F(n/2);当n>0

代码

递归的代码：

View Code

#include<stdio.h>
int fun(int n)
{
    if(n>0)
        return n*fun(n/2);
    else
        return n+1;
}
int main()
{
  int n;
  printf("请输入n的值：\n");
  scanf("%d",&n);
  printf("%d\n",fun(n));
 return 0;
}

非递归的代码：

View Code

 1 int main()
 2 {
 3   int n,s=1;
 4   printf("请输入n的值：\n");
 5   scanf("%d",&n);
 6   while(n>0)
 7   {
 8     s=s*n;
 9     n=n/2;
10   }
11   printf("%d\n",s);
12  return 0;
13 }

总结

递归算法，弄清楚其中的逻辑关系。