尾递归是个什么鬼

了解尾递归之前，先了解一下尾调用。

在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位置为尾位置。（摘自维基百科）

以上的解释来自维基百科。介绍了什么叫尾调用。例如：

function foo(data) {
    a(data);
    return b(data);
}

　　

这里的a(data)和b(data)都是函数调用，但是b(data)是函数返回前的最后运行的东西，所以也是所谓的尾位置。例如：

function foo1(data) {
    return a(data) + 1;
}
function foo2(data) {
    var ret = a(data);
    return ret;
}
function foo3(data) {
    var ret = a(data);
    return (ret === 0) ? 1 : ret;
}

　　

这种就不是尾调用，对于foo1,最后一个动作是+1操作，并非是直接函数调用；对于foo3,是经过计算返回的结果，也不是尾调用。，foo2也不是尾调用

尾调用很重要的特性就是它可以不在调用栈上面添加一个新的堆栈帧，而是更新它。

接下来说一下什么是尾递归：

若一个函数在尾位置调用本身（或是一个尾调用本身的其他函数等），则称这种情况为尾递归，是递归的一种特殊情形。而形式上只要是最后一个return语句返回的是一个完整函数，它就是尾递归。这里注意：尾调用不一定是递归调用，但是尾递归一定是尾调用。

接下来通过斐波那契数列和阶乘来进一步理解尾递归的含义。

斐波那契数列

 常规的斐波那契数列算法可能是这样的：

int fib(int n) {
 
    if (n <= 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

　　

上面的这种递归计算最终的return操作是加法操作。所以不是尾递归。

如果用尾递归就是这样的：

/**
 计算第n位斐波那契数列的值
 
 @param n 第n个数
 @param acc1 第n个数
 @param acc2 第n与第n+1个数的和
 @return 返回斐波那契数列值
 */
int tailfib(int n,int acc1,int acc2) {
    if (n < 2) {
        return acc1;
    }
    
    return tailfib(n-1,acc2,acc1 + acc2); 
}

　　

比如我们想计算第10位斐波那契数列的值，只需要fib(10，1，1)即可。

看一下测试效果，测试程序如下：

int main(int argc, const char * argv[]) {
    clock_t start,finish;
   
    start = clock();
    printf("计算结果：%d\n", fib(45));
    finish = clock();
    printf("花费时间--------%lu\n",finish - start);
 
    
    start = clock();
    printf("计算结果：%d\n", tailfib(45,1,1));
    finish = clock();
    
    printf("花费时间--------%lu\n",finish - start);
    return 0;
    
}

　　

计算结果如下：

计算结果：1134903170
花费时间--------5540692
计算结果：1134903170
花费时间--------4
Program ended with exit code: 0

　　

效率可想而知。

 

阶乘

常规的计算阶乘的方法可能是这样的：

int fac(int n) {
    if (n == 1) {
        return 1;
    }
    return fac(n-1) * n;
}

复杂度为O(n)

尾递归的算法是这样的：

int tailfac(int n,int sum) {
    if (n == 1) {
        return sum;
    }
    return fac(n-1, n * sum);
}

 复杂度为O(1)

测试一下效率,测试程序如下：

int main(int argc, const char * argv[]) {
    clock_t start,finish;
   
    start = clock();
    printf("计算结果：%d\n", fac(16));
    finish = clock();
    printf("花费时间--------%lu\n",finish - start);
 
    
    start = clock();
    printf("计算结果：%d\n", tailfac(16,1));
    finish = clock();
    
    printf("花费时间--------%lu\n",finish - start);
    return 0;
    
}

　　

测试结果：

计算结果：2004189184
花费时间--------31
计算结果：2004189184
花费时间--------2

　　

尾递归效率比较高，但是个人觉得有尾递归算法理解起来会比较困难，你需要标注一下每个传入参数的作用，否则刚接触不一定会用这个算法。

 

参考资料：阮一峰的网络日志 维基百科

转载请标注来源：http://www.cnblogs.com/zhanggui/p/7722541.html