下面这个是尾递归:

function f(x) {
   if (x === 1) return 1;
   return f(x-1);
}

这个不是尾递归:

function f(x) {
   if (x === 1) return 1;
   return 1 + f(x-1);
}

在普通递归中,当递归进入下一层后,上一层的函数需要保存起来,等待递归返回后继续处理剩下的操作。

在尾递归中,当递归进入下一层后,上一层的函数可以不用保存,函数最终的结果就是最后一层的结果,这就可以节省非常多的内存资源。

需要注意的是,并不是所有语言都支持尾递归优化的,也就是说在某些语言中,尾递归同普通递归消耗的资源是同样多的。那么什么语言支持尾递归优化呢?

常见的语言中c,c++是支持尾递归优化的,Js从ES6开始在严格模式下支持尾递归优化,正常模式不支持。其他的常见语言如Java,Phthon,PHP,Ruby等都是不支持尾递归优化的。

在有尾递归优化的语言中,鼓励用尾递归来改写其他形式的递归;在没有尾递归优化的语言中,鼓励用迭代来改写尾递归,减少可能对内存的极端消耗。

下面是一个Python的尾递归例子:

def f(x):
    if x == 1:
        return 1;
    return f(x-1);

我们可以将其改成迭代的形式:

def f(x):
    while x!=1:
        x = x-1
    return x
posted @ 2019-02-22 11:33:35
评论加载中...

发表评论