尾递归是什么?有什么应用场景呢?——深入探究高级前端开发工程师必备技能

3 min read

尾递归是指一个函数的最后一条语句是递归调用。简单说就是函数调用发生在尾部(即函数的最后一步)。相比非尾递归,在执行递归调用时,尾递归不会在调用栈中添加新的帧,而是重复使用当前帧。这可以减少空间复杂度,并且可以提高程序的效率。

一个符合尾递归的函数例子是阶乘函数factorial(n)

def factorial(n, acc=1):
    if n == 0: 
        return acc
    else:
        return factorial(n-1, acc*n)

上述函数在执行过程中,每次迭代时都将计算值传递到下一次调用中,最终返回完整的结果。而且,尾递归具有明显的结果之前返回的优势,可以让编译器更容易地对其进行优化,提高执行效率。

应用场景:尾递归适用于需要迭代调用的场合,比如阶乘、斐波那契数列等,同时要求空间复杂度尽可能小,避免调用栈溢出等问题。同时,尾递归不适用于需要反复迭代来获取结果的场合,比如Map-Reduce算法。