递归时间比较

Benchmark created on


Description

1、迭代 2、 递归 3、记忆化递归 4、尾调用优化

Test runner

Ready to run.

Testing in
TestOps/sec
递归
function fibonacci(n) {
  if (n < 1) {
    return 0;
  }
  if (n <= 2) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
ready
迭代
function fibonacciIterative(n) {
  if (n < 1) { return 0; }
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) {
    fibN = fibNMinus1 + fibNMinus2;
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}
ready
记忆化
function fibonacciMemoization(n) {
  if (n < 1) { return 0; }
  const memo = [0, 1];
  const fibonacciMem = num => {
    if (memo[num] != null) { return memo[num]; }
    return (memo[num] = fibonacciMem(num - 1) + fibonacciMem(num - 2));
  };
  return fibonacciMem(n);
}
ready
尾调用
function fib(n) {
  return fibImp1(0, 1, n)
}
function fibImp1(a, b, n) {
  if (n === 0) return a
  return fibImp1(b, a + b, n - 1)
}
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.