Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

尾调用与尾递归 #20

Open
sunbigshan opened this issue Mar 27, 2019 · 0 comments
Open

尾调用与尾递归 #20

sunbigshan opened this issue Mar 27, 2019 · 0 comments
Labels

Comments

@sunbigshan
Copy link
Owner

sunbigshan commented Mar 27, 2019

什么是尾调用?

尾调用(Tail Call),顾名思义,是指在某个函数的最后一步是调用另一个函数,它是函数式编程中的一个重要概念。

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

上面代码中,函数 f 的最后一步调用了函数 g,这就叫做尾调用。

以下三种情况,都不属于尾调用:

// 情况一
function f(x){
  let y = g(x);
  return y;
}

// 情况二
function f(x){
  return g(x) + 1;
}

// 情况三
function f(x){
  g(x);
}

上述情况一中,函数调用之后还有赋值操作;情况二也一样,即使写在了同一行内,也在调用之后还有操作;而情况三等同于以下代码:

function f(x){
  g(x);
  return undefined;
}

尾调用不需要写在函数尾部,只要是执行的最后一步就好:

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

上面代码中,函数 mn 都属于尾调用,因为它们都是函数 f 的最后一步操作。

尾调用优化

我们知道,函数在执行时会生成与其相对应的函数执行上下文(又称“调用帧”,里面保存调用位置和内部变量等信息),并放入执行上下文栈(又称“调用栈”)的顶部。如果在函数 A 中调用函数 B,那么在 A 的调用帧上方,会生成一个 B 的调用帧,等 B 执行完毕,把结果返回 AB 的调用帧才会消失,如果 B 内部还调用了函数 C ,那么在 B 的上方还会继续生成 C 的调用帧。以此类推,继续循环调用下去的话,就有可能发生“栈溢出”。

由于尾调用是函数的最后一步操作,所以外层调用帧中的调用位置和内部变量都用不到了,也就是说,内层调用帧会直接取代外层调用帧,这样就可以做到每次执行时,调用帧只有一个,这将大大节省内存,也就是我们所说的“尾调用优化”。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

// 等同于
function f() {
  return g(3);
}
f();

// 等同于
g(3);

上面代码中,如果函数 g 不是尾调用,函数 f 就需要保存内部变量 mn 的值、g 的调用位置等信息。但由于调用 g 之后,函数 f 就结束了,所以执行到最后一步,完全可以删除 f(x) 的调用帧,只保留 g(3) 的调用帧。

注意,只有不再用到外层函数的内部变量,内层函数的调用帧才会取代外层函数的调用帧,否则就无法进行“尾调用优化”。

function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

上面的函数不会进行尾调用优化,因为内层函数 inner 用到了外层函数 addOne 的内部变量 one

什么是尾递归?

函数调用自身,叫做递归。如果尾调用自身,就叫做尾递归。

递归非常耗内存,因为要保留成百上千个调用帧,很容易发生“栈溢出”(stack overflow),但对于尾递归来说,只存在一个调用帧,所以不会发生“栈溢出”。

function factorial(n) {
  if(n === 1) return 1;
  return n * factorial(n -1);
}

factorial(5) // 120

上面代码是一个阶乘函数,计算n的阶乘,最多需要保存n个调用记录,复杂度 O(n)

如果改写成尾递归,只保留一个调用记录,复杂度 O(1) 。

function factorial(n, total) {
  if(n === 1) return total;
  return factorial(n -1, n * total);
}

factorial(5, 1) // 120

还有一个比较著名的例子,就是计算 Fibonacci 数列,也能充分说明尾递归优化的重要性。

非尾递归的 Fibonacci 数列实现如下。

function Fibonacci(n) {
    if(n <= 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出

尾递归优化过的 Fibonacci 数列实现如下:

function Fibonacci(n, arg1 = 1, arg2 = 1) {
    if(n <= 1) return arg2;
    return Fibonacci(n - 1, arg2, arg1 + arg2);
}
console.log(Fibonacci(10)) // 89
console.log(Fibonacci(100)) // 573147844013817200000
console.log(Fibonacci(1000)) // 7.0330367711422765e+208

递归函数的改写

尾递归的实现,往往需要改写递归函数,确保最后一步只调用自身。做到这一点的方法,就是把所有用到的内部变量改写成函数的参数。比如上面的例子,阶乘函数 factorial 需要用到一个中间变量 total,那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观,第一眼很难看出来,为什么计算5的阶乘,需要传入两个参数5和1?

两个方法可以解决这个问题。方法一是在尾递归函数之外,再提供一个正常形式的函数。

function tailFactorial(n, total) {
  if(n === 1) return total;
  return factorial(n -1, n * total);
}

function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5) // 120

函数式编程有一个概念,叫做柯里化(currying),意思是将多参数的函数转换成单参数的形式。这里也可以使用柯里化。

function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

第二种方法就简单多了,就是采用 ES6 的函数默认值。

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令,所有的循环都用递归实现,这就是为什么尾递归对这些语言极其重要。

严格模式

ES6 的尾调用优化只在严格模式下开启,正常模式是无效的。

这是因为在正常模式下,函数内部有两个变量,可以跟踪函数的调用栈。

  • func.arguments:返回调用时函数的参数。
  • func.caller:返回调用当前函数的那个函数。

尾调用优化发生时,函数的调用栈会改写,因此上面两个变量就会失真。严格模式禁用这两个变量,所以尾调用模式仅在严格模式下生效。

function restricted() {
  'use strict';
  restricted.caller;    // 报错
  restricted.arguments; // 报错
}
restricted();

尾递归优化的实现

尾递归优化只能在严格模式下生效,那么正常模式下,或者那些不支持该功能的环境中,有没有办法也使用尾递归优化呢?答案是可以的,我们可以自己实现尾递归优化。

原理很简单,尾递归之所以需要优化,就是因为调用帧太多,造成了调用栈溢出,那么只要减少调用栈,就不会溢出。怎么做可以减少调用栈呢?就是采用“循环”换掉“递归”。

下面是一个正常的递归函数:

function sum(x, y) {
    if(y > 0) {
        return sum(x + 1, y - 1);
    }
    return x;
}

sum(1, 100000); //  Maximum call stack size exceeded

蹦床函数(trampoline)可以将递归执行转为循环执行。

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

function sum(x, y) {
    if(y > 0) {
        return sum.bind(null, x + 1, y - 1);
    }
    return x;
}

trampoline(sum(1, 100000)); // 100001

sum 函数的每次执行,都会返回自身的另一个版本,因此不会发生栈溢出。

蹦床函数并不是真正的尾递归优化,下面的实现才是。

function toc(f) {
    var value,
          active = false,
          accumulated = [];

    return function() {
        accumulated.push(arguments);
        if(!active) {
            active = true;
            while(accumulated.length) {
                value = f.apply(this, accumulated.shift());
            }
            active = false;
            return value;
        }
    }
}

var sum = toc(function(x, y) {
    if(y > 0) {
        return sum(x + 1, y - 1);
    }
    return x;
})

sum(1, 100000) // 100001

上面代码中,tco 函数是尾递归优化的实现,它的奥妙就在于状态变量 active。默认情况下,这个变量是不激活的。一旦进入尾递归优化的过程,这个状态就会被激活。然后,每一轮递归 sum 返回的都是 undefined,所以就避免了递归执行;而 accumulated 数组存放每一轮 sum 执行的参数,总是有值的,这就保证了 accumulator 函数内部的 while 循环总是会执行。这样就很巧妙的将“递归”改成了“循环”,而最后一轮的参数会取代前一轮的参数,保证了调用栈只有一层。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant