经典递归求阶层改造

经典的求阶层算法可能如下：

long f(long n)...{
   if(n==1) return 1;
  else return n*f(n-1) ;
}

当我们求100的阶层时，这个程序就算改成用double类型声明n也会溢出的。怎么办呢？我们知道一个数n的阶层，要求n+1的阶层时，可以用我们做乘法时的方法：每一位分别乘以这个数，然后进位。这样我们可以想到把n的阶层按位存放在一个数组中，然后遍历数组按位乘，最后规格化（分别进位），保证做完的n+1的阶层仍然按位保存在那个数组中就可以了。

核心代码如下：

function(n-1);  /*递归，可能开销大，哪位有兴趣用栈改写下*/
 for(i=0;i<LENGTH;i++) /*分别按位乘n*/
  result[i]=result[i]*n;

 for(i=0;i<LENGTH;i++){
   for(j=i,a=result[i],result[i]=0;a>0;j++){        /*将每一位分别向前进位，可能产生新的最高有效位*/
      result[j]=a%10+result[j];
      a=a/10;
   }
  if(j>LENGTH) /*新的最高有效位*/
     LENGTH=j;
 }

下面是我做的个演示程序，在TC2.0（很老的dos软件了，呵）下调试成功。欢迎大家指点。

/* To calculate a number's jieceng using recursion
 * author@ M.Liang Liu
 *          helped by  Hou Z.Hai
 * 2006-08-18
 */

#include<stdlib.h>
#include<stdio.h>
int LENGTH=1;/*数组的有效长度，毕竟有部分是双重循环啊！*/
int result[1000]={0};     /*全局变量：软件科学告诉我们尽量少用全局变量，这里为了方便*/

void function(int n){
/*multify and format.*/
     int i,j,a;
  if(n==1) {
   result[0]=1;
   return;
 }
 function(n-1);
 for(i=0;i<LENGTH;i++)
  result[i]=result[i]*n;

 for(i=0;i<LENGTH;i++){
   for(j=i,a=result[i],result[i]=0;a>0;j++){
      result[j]=a%10+result[j];
      a=a/10;
   }
  if(j>LENGTH)
     LENGTH=j;
 }
 return;
}

main()
{
   int n,i;
   clrscr();
   printf(" Please input the number: ");
   scanf("%d",&n);
   function(n);
   printf(" ********************************************************* "); 
   printf("  The number's jiecheng is:");
   printf("           ===========================                     ");
   for(i=LENGTH-1;i>=0;i--)
     printf("%d",result[i]);
   printf("           ============================                     ");
   printf("The jiecheng has %d bits.",LENGTH);
   getchar();
   getchar();
}