Aaron学习笔记

少壮不努力,长大没饭吃!
posts - 4, comments - 13, trackbacks - 0, articles - 37

求N的阶乘,对于阶乘,一般的递归运算的函数可以为

long factorial(int n){
    
if(n <= 1)
        
return 1;
    
else 
        
return n * factorial(n-1);
}
而非递归的运算函数可以表示为
long factorial( int n )
{
    
int    result = 1;

    
while( n > 1 ){
        result 
*= n;
        n 
-= 1;
    }


    
return result;
}
菲波那锲数列的定义都知道吧,是这样子的
它的递归函数都会写
long
fibonacci( 
int n )
{
   
if( n <= 2 )
      
return 1;
   
else
      
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}

但是它的递归函数实在效率太低,重复计算的值相当的多,所以我们需要改进,使用循环
long
fibonacci( int n )
{
    long    next_older_result = 0;
    long    previous_result = 1;
    long    result = 1;

    if( 1 == n)
        return 0;
    else if( 2 == n)
        return 1;
    int i = 2;
    while(i < n){
        i++;
        next_older_result = previous_result;
        previous_result = result;
        result = previous_result + next_older_result;
    }
    return result;
}
如果你仔细观察一下,你会发现以上两个的递归调用都是函数所执行的最后一项任务。这个函数是尾部递归
尾部递归很容易也成非递归的形式。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理