javaScript递归函数

发表于 更新于

今天找了一些资料重温了一下 JavaScript 的递归函数，写个博客记录一下。

首先什么是递归

递归是一项非常重要的编程技巧，函数通过它调用其本身。 —msdn 文档介绍

举个例子,常用的乘阶。

1
2
3
4
5
function factorial(i) {
  if (i === 1) return i;
  return i * factorial(i - 1);
}
console.log(factorial(5)); // 5*4*3*2*1

分几个步骤

  1. 声明一个函数 factorial，接受一个参数 i。
  2. 判断 i 是否等于 1，如果等于 1 则直接返回 i。
  3. 如果 i 不等于 1，则返回 i * factorial(i - 1)，再次调用函数本身。(如此如果严格可以判断 i 是否大于等于 0）
    然后函数就会重复 2 - 3 两个步骤，直至 i 减到 1 为止。

本身递归调用到此结束，在学习的过程中发现了其他资料。

JavaScript 执行上下文栈

看的是这个教程

JavaScript 执行顺序。

1
2
3
4
5
6
7
8
9
10
11
12
var foo = functiom () {
	console.log('foo1')；
}
foo();

var foo = functiom () {
	console.log('foo2')；
}
foo();
最后会打印出
foo1
foo2

解释一下这个为什么不会被覆盖。

1
2
3
4
5
6
7
8
9
10
上面的代码写成这样就比较好理解;
var foo;
foo = function() {
  console.log("foo1");
};
foo();
foo = function() {
  console.log("foo2");
};
foo();
1
2
3
4
5
6
7
8
9
10
11
function foo() {
  console.log("foo1");
}

foo(); // foo2

function foo() {
  console.log("foo2");
}

foo(); // foo2

在解释一下这个

1
2
3
4
5
6
7
8
function foo() {
  console.log("foo1");
}
function foo() {
  console.log("foo2");
}
foo(); // foo2
foo(); // foo2

函数被提升之后第二个覆盖了第一个，这是 JavaScript 作用域提升。
JavaScript 的可执行代码有三种，全局代码，函数代码，eval 代码
当执行到一个函数的时候就会进行准备工作，叫做执行上下文。
原博客把执行上下文说的很清楚了，我理解了一部分。有兴趣可以点击上面的连接继续了解，继续讲递归。

尾调用

根据上面的知识，以及以前的知识，我们都知道递归会消耗大量内存，之执行一个函数就压入上下文栈，直至递归结束才会释放，造成递归占用大量内存。

原博客介绍

尾调用，是指函数内部的最后一个动作是函数调用，改调用的返回值，直接返回给函数。

1
2
3
4
function f(x) {
  return g(x);
}
// 尾调用
1
2
3
4
5
function f(x) {
  return g(x) - 1;
}

// 非尾调用

用上面的上下文栈，来看第二个函数，函数 f 执行指挥返回一个 g 函数而 g 函数的结果需要 f 函数作用域内 - 1 才是结果，导致引用的时候 g 函数入栈的时候会持有 f 函数的作用域，f 得不到释放，一直等 g 函数结束之后才会被释放。

现在优化一下上面的递归

1
2
3
4
5
function factorial(i, res) {
  if (i === 1) return res;
  return factorial(i - 1, i * res);
}
console.log(factorial(4, 1));

这样优化函数，保持返回的函数没有上个函数的引用，这样上个函数在入栈之后执行到 return 之后就会被释放，而不会和上面的递归一样等到最终结果才会被释放。（ps。JavaScript 上下文栈，需要好好看看比较重要）