首页  |  Linux  |  C/C++  |  网络编程  |  Python   |  Algorithm  |  数据库  |  经验  |   人生 & 随想   |  站内搜索  |  关于

<<< previous

该文已被浏览1129

Tail Recursion & Tail Call Elimination



什么是 Tail Recursion?

Tail Recursion 是在一个递归函数中,递归调用是该递归函数所要做的最后一件事情。下面的递归函数即是一个 Tail Recursion:
// 下面的函数打印 0~n 之间的值
void print(int n)
{
    if(n < 0)
        return;
    cout<<n<<" ";
    print(n-1);
}
注意,下面的递归函数不是一个 Tail Recursion:
// 下面这个函数计算 1+2+...+n 的和
int foo(int n)
{
    if(n == 1)
        return 1;
    return n+sum(n-1);
}
上面的递归函数不是 Tail Recursion 的原因在于递归调用不是该递归函数要做的最后一件事情,sum(n-1) 返回的值还要为 sum(n) 所用。

Tail Recursion 的优点

Tail Call Elimination

Tail Call Elimination 是对 Tail Recursion 递归函数的一种优化,采用的优化方式一般为将 Tail Recursion 递归函数的最后一句递归调用使用 goto 语句来替换掉。下面是对上述的 print() 函数进行 Tail Call Elimination 的一个例子:
// 下面的函数打印 0~n 之间的值            
void print(int n)
{
start:
    if(n < 0)
        return;
    cout<<n<<" ";
    // 下面两条语句替换了之前的递归调用
    --n;
    goto start;
}
另外,快速排序也是应用了 Tail Recursion,而归并排序并不是 Tail Recursion, 这也是快速排序表现更好的一个原因.
更新:快速排序优化:降低最差情况的空间复杂度 一文中,会介绍如何利用 Tail Call Elimination 来降低快速排序的最差空间复杂度。

一如既往,如果你对文章中的内容有任何疑问,或者是发现文章中有任何错误,都可以通过下面的地址发邮件告诉我.
E-mail: contact@TechForGeek.info