与复杂度有关的问题

数据结构与算法

以斐波那契数列为例子
普通的递归版本
int fab(int n){
    if(n<3)
        return 1;
    else
        return fab(n-1)+fab(n-2);  
}
具有"线性迭代过程"特性的递归---尾递归过程
int fab(int n,int b1=1,int b2=1,int c=3){
    if(n<3)
        return 1;
    else {
        if(n==c)
             return b1+b2;
        else
             return fab1(n,b2,b1+b2,c+1);
    }
}
以fab(4)为例子
普通递归fab(4)=fab(3)+fab(2)=fab(2)+fab(1)+fab(2)=3  6次调用
尾递归fab(4,1,1,3)=fab(4,1,2,4)=1+2=3                         2次调用