递归和堆栈

递归是一种编程模式，在一个任务可以自然地拆分成多个相同类型但更简单的任务的情况下非常有用。或者，在一个任务可以简化为一个简单的行为加上该任务的一个更简单的变体的时候可以使用。或者，就像我们很快会看到的那样，处理某些数据结构。

当一个函数解决一个任务时，在解决的过程中它可以调用很多其它函数。在部分情况下，函数会调用 自身。这就是所谓的 递归。

### 实现指定数字的n次方
编写一个函数pow(x,n),实现类似Math.pow的方法
* 使用循环
* 使用递归

**循环**
```js
var pow2 = (x, n) => {
    var result = 1;
    for(let i=0; i<n; i++){
        result *=x;
    }
    return result;
}
```

**递归**
```js
// 简化任务，调用自身
var pow = (x,y) => {
    if(y== 1) {
        return x;
    }
    return x * pow(x, y-1);
}
```

递归的变体在本质上是不同的
```js
              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)
```

如果 n == 1，所有事情都会很简单，这叫做 基础 的递归，因为它会立即产生明显的结果：pow(x, 1) 等于 x。
否则，我们可以用 x * pow(x, n - 1) 表示 pow(x, n)。在数学里，可能会写为 xn = x * xn-1。这叫做 一个递归步骤：我们将任务转化为更简单的行为（x 的乘法）和更简单的同类任务的调用（带有更小的 n 的 pow 运算）。接下来的步骤将其进一步简化，直到 n 达到 1。
我们也可以说 pow 递归地调用自身 直到 n == 1。

> 最大的嵌套调用次数（包括首次）被称为 递归深度。在我们的例子中，它正好等于 n。
最大递归深度受限于 JavaScript 引擎。对我们来说，引擎在最大迭代深度为 10000 及以下时是可靠的，有些引擎可能允许更大的最大深度，但是对于大多数引擎来说，100000 可能就超出限制了。有一些自动优化能够帮助减轻这种情况（尾部调用优化），但目前它们还没有被完全支持，只能用于简单场景。
这就限制了递归的应用，但是递归仍然被广泛使用。有很多任务中，递归思维方式会使代码更简单，更容易维护。

### 执行上下文和堆栈

现在我们来研究一下递归调用是如何工作的。为此，我们会先看看函数底层的工作原理。

有关正在运行的函数的执行过程的相关信息被存储在其 执行上下文 中。

执行上下文 是一个内部数据结构，它包含有关函数执行时的详细细节：当前控制流所在的位置，当前的变量，this 的值（此处我们不使用它），以及其它的一些内部细节。

一个函数调用仅具有一个与其相关联的执行上下文。

当一个函数进行嵌套调用时，将发生以下的事儿：

* 当前函数被暂停；
* 与它关联的执行上下文被一个叫做 执行上下文堆栈 的特殊数据结构保存；
* 执行嵌套调用；
* 嵌套调用结束后，从堆栈中恢复之前的执行上下文，并从停止的位置恢复外部函数。

**任何递归都可以用循环来重写。通常循环变体更有效。**

### 递归遍历
递归的另一个重要作用就是遍历

假设我们有一个人才表，结构如下：
```js
et company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};
```

**递归求和**
```js
function sumtoCompany(data) {
    if(Array.isArray(data)) {
        return data.reduce((acc, curr) => acc + curr.salary, 0);  // 但数组情况
    } else {
        let sum = 0;
        for(let sub of Object.values(data)) {
            sum += sumtoCompany(sub); // 递归调用所有子部门，对结果求和
        }
        return sum;
    }
}
```


### 递归结构
链表也是递归的一种数据结构

**总结**

* 递归 是编程的一个术语，表示从自身调用函数（译注：也就是自调用）。递归函数可用于以更优雅的方式解决问题。

当一个函数调用自身时，我们称其为 递归步骤。递归的 基础 是函数参数使任务简单到该函数不再需要进行进一步调用。

* 递归定义 的数据结构是指可以使用自身来定义的数据结构。

例如，链表可以被定义为由对象引用一个列表（或 null）而组成的数据结构

任何递归函数都可以被重写为迭代（译注：也就是循环）形式。有时这是在优化代码时需要做的。但对于大多数任务来说，递归方法足够快，并且容易编写和维护。

----

### 对数字求和到给定值
编写一个函数 sumTo(n) 计算 1 + 2 + ... + n 的和。
用三种方式实现：

* 使用循环。
* 使用递归，对 n > 1 执行 sumTo(n) = n + sumTo(n-1)。
* 使用 等差数列 求和公式.

**使用循环的解法**
```js
function sumTo1(n) {
    let sum = 0;
    for(var i=n; i>0; i--){
        sum += i
    }
    return sum;
}
```

**使用递归的解法**
```js
function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}
```

**使用等差数列**
```js
// 使用公式 sumTo(n) = n*(n+1)/2 的解法
function sumTo(n) {
  return n * (n + 1) / 2;
}
```

> P.S. 当然是公式解法最快。对任何数字 n，只需要进行 3 次运算。数学大法好！
循环的速度次之。在循环和递归方法里，我们对相同的数字求和。但是递归涉及嵌套调用和执行堆栈管理。这也会占用资源，因此递归的速度更慢一些。

----

### 计算阶乘
自然数的 阶乘 是指，一个数乘以 数字减去 1，然后乘以 数字减去 2，以此类推直到乘以 1。n 的阶乘被记作 n!。

换句话说，factorial(n) 的结果可以用 n 乘以 factorial(n-1) 的结果来获得。对 n-1 的调用同理可以依次地递减，直到 1。
```js
function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}
```
----

### 斐切那波数
斐波那契数 序列有这样的公式： Fn = Fn-1 + Fn-2。换句话说，下一个数字是前两个数字的和。

前两个数字是 1，然后是 2(1+1)，然后 3(1+2)，5(2+3) 等：1, 1, 2, 3, 5, 8, 13, 21...。

斐波那契数与 黄金比例 以及我们周围的许多自然现象有关。

编写一个函数 fib(n) 返回第 n 个斐波那契数。

示例
```js
function fib(n) { /* 你的代码 */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
```

我们可以尝试的第一种解法是递归。斐波那契数根据定义是递归的：
```js
function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
```
……但是 n 比较大时会很慢。比如 fib(77) 会挂起引擎一段时间，并且消耗所有 CPU 资源。因为函数产生了太多的子调用。同样的值被一遍又一遍地计算

改用动态规划
```js
function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}
```
----

### 单链表遍历
假设我们有一个单链表
```js
let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};
```
编写一个可以逐个输出链表元素的函数 printList(list)。使用两种方式实现：循环和递归。
哪个更好：用递归还是不用递归的？

**循环解法**
```js
function getListVal2(o) {
    var source = o;
    while(source) {
        console.log(source.value);
        source = source.next;
    }
}
```
**递归解法**
```js
function getListVal(o) {
    if(o.value) {
        console.log(o.value);
    }
    if(o.next) {
        getListVal(o.next);
    }
}
```
哪个更好呢？
> 从技术上讲，循环更有效。这两种解法的做了同样的事儿，但循环不会为嵌套函数调用消耗资源。
另一方面，递归解法更简洁，有时更容易理解。

----

### 反向输出单链表
反向输出前一个任务 输出一个单链表 中的单链表。
使用两种解法：循环和递归。

**递归**
```js
function reGetListVal(o) {
    if(o.next) {
        reGetListVal(o.next);
    }
    console.log(o.value);
}
```

**循环**

循环解法也比直接输出稍微复杂了点儿。
在这而没有什么方法可以获取 list 中的最后一个值。我们也不能“从后向前”读取。
因此，我们可以做的就是直接按顺序遍历每个元素，并把它们存到一个数组中，然后反向输出我们存储在数组中的元素：

```js
function reGetListVal2(o) {
    var arr = [];
    var temp = o;
    while(temp) {
        arr.push(temp.value);
        temp = temp.next;
    }
    arr.reverse().map(e => console.log(e));
}
```
> 请注意，递归解法实际上也是这样做的：它顺着链表，记录每一个嵌套调用里链表的元素（在执行上下文堆栈里），然后输出它们。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

递归和堆栈 #38

实现指定数字的n次方

执行上下文和堆栈

递归遍历

递归结构

对数字求和到给定值

计算阶乘

斐切那波数

单链表遍历

反向输出单链表

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

递归和堆栈 #38

Description

实现指定数字的n次方

执行上下文和堆栈

递归遍历

递归结构

对数字求和到给定值

计算阶乘

斐切那波数

单链表遍历

反向输出单链表

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions