# JavaScript 中的尾调用

## 尾调用(Tail Call)

```function f(x) {
return g(x)
}```

```function f(x) {
return 1 + g(x)
}```

`[f(x)] => [g(x)]`

`[f(x)] => [1 + g(x)]`

## 尾递归

`0, 1, 1, 2, 3, 5, 8, 13, 21, ...  `

```function fibonacci(n) {
if (n === 0) return 0
if (n === 1) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}```

```[fibonacci(5)]
[fibonacci(4) + fibonacci(3)]
[(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))]
[((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))]
[fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)]
[1 + 0 + 1 + 1 + 0 + 1 + 0 + 1]
5```

```function fibonacciTail(n, a = 0, b = 1) {
if (n === 0) return a
return fibonacciTail(n - 1, b, a + b)
}```

```fibonacciTail(5) === fibonacciTail(5, 0, 1)
fibonacciTail(4, 1, 1)
fibonacciTail(3, 1, 2)
fibonacciTail(2, 2, 3)
fibonacciTail(1, 3, 5)
fibonacciTail(0, 5, 8) => return 5```

## 尾递归优化

### 改写为循环

```function fibonacciLoop(n, a = 0, b = 1) {
while (n--) {
[a, b] = [b, a + b]
}
return a
}```

### 蹦床函数

```function trampoline(f) {
while (f && f instanceof Function) {
f = f()
}
return f
}```

```function fibonacciFunc(n, a = 0, b = 1) {
if (n > 0) {
[a, b] = [b, a + b]
return fibonacciFunc.bind(null, n - 1, a, b)
} else {
return a
}
}

trampoline(fibonacciFunc(5)) // return 5
```

### 实际的尾递归优化

```function tailCallOptimize(f) {
let value,
active = false
const accumulated = []
return function accumulator() {
accumulated.push(arguments)
if (!active) {
active = true
while (accumulated.length) {
value = f.apply(this, accumulated.shift())
}
active = false
return value
}
}
}```

```const fibonacciTail = tailCallOptimize(function(n, a = 0, b = 1) {
if (n === 0) return a
return fibonacciTail(n - 1, b, a + b)
})
fibonacciTail(5) // return 5```

1. 首先通过闭包，在 tailCallOptimize 的作用域中保存唯一的 active 和 accumulated，其中 active 指示尾递归优化过程是否开始，accumulated 用来存放每次递归调用的参数，push 方法将参数入列，shift 方法将参数出列，保证先进先出顺序执行。
2. 经过 tailCallOptimize 包装后返回的是一个新函数 accumulator，执行 fibonacciTail 时实际执行的是这个函数，第一次执行时，现将 arguments0 推入队列，active 会被标记为 true，然后进入 while 循环，取出 arguments0。在 while 循环的执行中，会将参数类数组 arguments1 推入 accumulated 队列，然后直接返回 undefined，不会递归调用增加调用栈。
3. 随后 while 循环会发现 accumulated 中又多了一个 arguments1，然后再将 arguments2 推入队列。这样，在 while 循环中对 accumulated 的操作就是放进去一个、拿出来一个、再放进去一个、再拿出来一个，以此类推。
4. 最后一次 while 循环返回的就是尾递归的结果了。

## 问题

### 表达式中的尾调用

ES6 的箭头函数可以使用一个表达式作为自己的函数体，函数返回值就是这个表达式的返回值，在表达式中，以下几种情况可能包含尾调用：

`const a = x => x ? f() : g()`

```const a = x => {
if (x) {
return f()
} else {
return g()
}
}```

### 逻辑运算符（|| 与 &&）

`const a = () => f() || g()`

```const a = () => {
const result = f()
if (result) {
return result
} else {
return g()
}
}```

`||` 运算符的结果依赖于 f 函数的返回值，而不是直接返回 f 的返回值，直接返回的只有 g 函数的返回值。`&&` 运算符的情况也同理：

`const a = () => f() && g() `

```const a = () => {
const result = f()
if (!result) {
return result
} else {
return g()
}
}```

### 逗号运算符（,）

`const a = () => (f(), g()) `

```
const a = () => {
f()
return g()
}```

### 单独的函数调用不是尾调用

```function foo() {
bar()
}```

```function foo() {
bar()
return undefined
}```

### Return Continue

```function factorial(n, acc = 1) {
if (n === 1) {
return acc;
}

return continue factorial(n - 1, acc * n)
}

let factorial = (n, acc = 1) => continue
n == 1 ? acc
: factorial(n - 1, acc * n);

// or, if continue is an expression form:
let factorial = (n, acc = 1) =>
n == 1 ? acc
: continue factorial(n - 1, acc * n);```

### Function sigil

```// # sigil, though it's already 'claimed' by private state.
#function() { /* all calls in tail position are tail calls */ }

// Note that it's hard to decide how to readably sigil arrow functions.

// This is probably most readable.
() #=> expr
// This is probably most in line with the non-arrow sigil.
#() => expr

// rec sigil similar to async functions
rec function() { /* likewise */ }
rec () => expr```

### !-return

```function () { !return expr }

// It's a little tricky to do arrow functions in this method.
// Obviously, we cannot push the ! into the expression, and even
// function level sigils are pretty ugly.

// Since ! already has a strong meaning, it's hard to read this as
// a tail recursive function, rather than an expression.
!() => expr

// We could do like we did for # above, but it also reads strangely:
() !=> expr```