search

YBFACC / blog

仅记录个人学习使用
3 stars 0 forks source link

尾递归 #23

Open YBFACC opened 4 years ago

YBFACC commented 4 years ago

尾递归(tail call optimisation)

尾递归解决的问题

递归的次数太多了，超过了程序承载的能力。

我通过一个简易的代码，来测试下函数调用栈的能力。

function f(n) {
  try {
    return f(n + 1)
  } catch (error) {
    console.log(n)
  }
}

f(1)

我的node环境上限大概是10000左右。

实际看一下调用栈。在浏览器中执行以下代码。

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  test
</body>
<script>

  function factorial(n, total = 1) {
    console.trace()
    if (n === 1) return total
    return factorial(n - 1, n + total)
  }

  console.log(factorial(30000))

</script>

</html>

628-2_change

可以看到函数调用栈里的数量逐渐增加。

使用尾递归

现在对尾递归的支持并不好。浏览器只有Safari支持，而且你必须开启严格模式。

你可以使用这个网站来查看支持性。

特征

测试

我们在Safari 中执行以下代码：

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  test
</body>
<script>
  'use strict'
  function factorial(n, total = 1) {
    console.trace()
    if (n === 1) return total
    return factorial(n - 1, n + total)
  }

  console.log(factorial(30000))

</script>

</html>

628-5_change

可以看到成功运行了，并且函数调用栈道数量一直没有发生变化。

例子

以下代码copy来自尾调用优化

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

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

factorial(5) // 120
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
function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

参考

尾递归的后续探究

尾调用优化