递归与尾递归 | 踏浪 - 前端技术分享

在介绍递归与尾递归之前，我们来看看递归的定义：程序调用自身的编程技巧称为递归（ recursion）

百度对递归的定义：递归

接着，我们再来看看一道题

1	编写一个函数fn，接收一个或者多个参数，其中一个参数为n，若 n=0 或者 n=1，函数返回 1，否则函数返回 1+2+3+...+(n-1)+n 的总和

递归

按照我们一般的思维，很快就能想到使用递归函数来解决这个问题，所以来看看递归是怎么解决的呢

function fn(n){
 if( n === 0 || n === 1 ){
   return 1
 }
 return n + fn(n - 1)
}

如果 n=5 那么上面的函数运行流程

n = 5 ==> 5 + fn(5 - 1)
n = 4 ==> 5 + 4 + fn(4 - 1)
n = 3 ==> 5 + 4 + 3 + fn(3 - 1)
n = 2 ==> 5 + 4 + 3 + 2 + fn(2 - 1)
n = 1 ==> 5 + 4 + 3 + 2 + 1

即：最后的结果是 5 + 4 + 3 + 2 + 1 = 15

可以看到，一般的递归，每一级递归都需要调用函数，同时这个函数还与其他的表达式运算，那这样的递归每一次都会创建新的栈。

随着递归深度的增加，创建的栈越来越多，最终造成爆栈

boom

所以，递归虽然可以解决很多问题，但是也需要注意一下使用限制。

#尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。

百度定义：尾递归

尾递归基于函数的尾调用（尾调用：返回一个函数并且调用这个函数）, 每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归!

同样的问题，使用尾递归的来看看

function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return fn(n -1, total + n)
}

同样是 n=5，来看看运行过程

n = 5 ==> fn(5, 1)
n = 4 ==> fn(4, 6)
n = 3 ==> fn(3, 10)
n = 2 ==> fn(2, 13)
n = 1 ==> fn(1, 15)

上面的运行每一次都是返回的一个单独的函数，没有其他的表达式与这个函数的结果运行，每一级递归的函数调用变成”线性”的形式。

上面就是关于一般递归与尾递归的说明。但是这里存在一个很大的问题，那就是JavaScript的 V8引擎对尾递归的优化做的并不好，上面的代码尾递归还不如一般的递归。虽然在JavaScript中无法运行，但是其他的语言例如Java，C，C++等，使用尾递归的好处多余一般递归。

手动优化

既然我们在JavaScript中无法使用尾递归，使用递归也害怕爆栈，那我们可以自己来一些方法实现相同的效果，例如上面的多个值相加

方案一：修改函数内部，使用循环

// n 是 正整数
function fn(n, a=0, b=1){
  while (n--) {
    [a, b] = [b, a + b]
  }
  return a
}

这个方法采用了ES6中的解构赋值。如果你不了解结构复制，可以去看看，如果你了解结构复制，那么上面的你就很容易理解了。

其实这种优化方法就是支持尾递归运行的这些引擎对相应语言的优化，使用循环优化，只是JavaScript V8 中没有相应的优化。说白了，就是想Java等语言已经有人帮你做了这一步。

方案二：蹦床函数

这是上面的尾递归的变形

// 尾递归代码
function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return fn(n -1, total + n)
}

这里我们来求一下 n=3 的时候的值，如果是使用尾递归，那么 n = 3 ==> 6

首先来了解一下什么是蹦床函数，先来看一段代码

function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return function(){
    return fn(n -1, total + n)
  }
}

同样是 n=3

// n = 3
fn(3) ==> Function
fn(3)() ==> Function
fn(3)()() ==> 6

从上面可以看到，如果 n 不是3而是一个很大的数字，那么我们就需要调用很多次函数调用来实现。为了简便，我们可以把这种调用形式写成函数，这样的函数就是蹦床函数。

// 蹦床函数
function trampoline(func, n){
  let result = func.call(func, n)
  while ( typeof result === 'function' ){
    result = result()
  }
  return result
}

这个蹦床函数有两个参数，第一个参数是一个函数，即我们需要实现逻辑的函数，本例中就是

function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return function(){
    return fn(n -1, total + n)
  }
}

使用蹦床函数代码耗时相对较长。

以上就是关于递归与尾递归的说明以及优化，当然，如果你要更好的方案，欢迎在评论区留言。