【前端知识之JS】尾递归的理解_js尾递归

前言

本系列主要整理前端面试中需要掌握的知识点。本节介绍对尾递归的理解，以及一些主要的应用例子。

一、什么是尾递归

• 尾递归，即在函数尾位置调用自身（或是一个尾调用本身的其他函数等等）。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数；
• 尾递归的两个特征：
  • 在尾部调用的是函数自身；
  • 可通过优化，使得计算仅占用常量栈空间。
• 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出
• 这时候，就可以使用尾递归，即一个函数中所有递归形式的调用都出现在函数的末尾，对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误，例子如下：

//普通递归求阶乘：如果n等于5，这个方法要执行5次，才返回最终的计算表达式，这样每次都要保存这个方法，就容易造成栈溢出，复杂度为O(n)
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

//尾递归求阶乘：每一次返回的就是一个新的函数，不带上一个函数的参数，也就不需要储存上一个函数了。尾递归只需要保存一个调用栈，复杂度 O(1)
function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、应用场景

1、数组求和

function sumArray(arr,total){
    if(arr.length === 1){
        return total
    }
    return sumArray(arr,total+arr.pop())
}

console.log(sumArray([1,2,3,4],0));
1
2
3
4
5
6
7
8

2、优化斐波那契数列

function factorial2(n,start=1,total=1){
    if(n<2){
        return total
    }
    return factorial2(n-1,total,total+start)
}
console.log(factorial2(5));
1
2
3
4
5
6
7

3、数组扁平化

function flat(arr=[],result=[]){
    arr.forEach(item =>{
        if(Array.isArray(item)){
            result = result.concat(flat(item,[]))
        }
        else{
            result.push(item)
        }
    })
    return result
}
console.log(flat(a));
1
2
3
4
5
6
7
8
9
10
11
12