函数进阶

递归和推栈

• 首先我们看一下函数底层工作原理：

  执行上下文：是一个内部数据结构，包含有关函数执行时的详细细节（控制流所在位置，当前变量，this的值，以及一些内部的细节

  当函数嵌套调用时：

  1. 当前函数被暂停
  2. 相关的执行上下文被 执行上下文堆栈 的特殊数据结构保存
  3. 执行嵌套调用
  4. 调用结束都，再从堆栈中恢复执行上下文，并从停止的位置恢复外部函数

递归

• 简要讲一下递归，递归就是上面的函数嵌套调用模式，不断的将当前的上下文压入堆栈的顶端，执行嵌套后的操作；当运行到出口return 时，在从堆栈的顶部一个个的恢复执行的过程

• 所有的递归算法，都可以用循环算法实现，两者的区别

  循环算法：一般情况下更加节省内存，更快；但代码结构不如递归直观

  递归算法：算法很直观，易于维护；但占内存大

更好的理解递归：我们引入链表

链表

• 为什么要引入链表？链表这一数据类型在js中不常使用，一般都会使用数数组来，存储数据，但是，当我们使用arr.unshift(obj) 操作必须对所有元素重新编号以便为新的元素 obj 腾出空间，而且如果数组很大，会很耗时。

  如果我们确实需要快速插入/删除，则可以选择另一种叫做 [链表]的数据结构

• 链表元素：是一个使用递归定义的对象

  let list = {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: {
          value: 4,
          next: null
        }
      }
    }
  };

  

  通过建立了这么一个链式结构：我们对插入删除元素更加的方便

  >//比如：头插数据，删除中间节点
  >let list = { value: 1 };
  >list.next = { value: 2 };
  >list.next.next = { value: 3 };
  >list.next.next.next = { value: 4 };
  
  >list = { value: "new item", next: list };	// 将新值添加到链表头部
  >list.next = list.next.next;					//删除value=1的节点

  链表的缺点：

  • 不能和数组一样通过下表快速查找引用

  升级的链表：

  • 双向链表：添加一个prev属性指向前一个节点，尾部加一个tail 变量指向尾部节点（尾部节点变化时，实时更新）

• 实例比较:

  1. 斐波那契数

  //递归算法
  function fib (n) {
  	return n <= 1 ? n: fib(n-1) + fib(n-2);
  }
  
  //循环算法（自下而上动态递归）
  function fib (n) {
      let a = 1;
      let b = 1;
      
      for (let i = 2; i < n ; i++) {
          let c = a + b;
          a = b;
          b = c; 
      }
      return b;
  }
  
  //两种算法直观看起来，递归逻辑关系非常的简单，但性能方面有一定的差距
  //递归算法，算n较大时，非常的慢，而且很占内存！！  比如fib(77);非常慢  

  2. 反向输出链表

  let list = {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: {
          value: 4,
          next: null
        }
      }
    }
  };
  
  //递归：使用先遍历，后输出，天然使用上下堆栈的恢复特点
  function printReverseList(list) {
  
    if (list.next) {
      printReverseList(list.next);
    }
  
    alert(list.value);
  }
  
  printReverseList(list);
  
  //循环操作：实际上也是新建了一个上下堆栈，存储对应的输出，然后，倒叙循环输出
  function printReverseList(list) {
    let arr = [];
    let tmp = list;
  
    while (tmp) {
      arr.push(tmp.value);
      tmp = tmp.next;
    }
  
    for (let i = arr.length - 1; i >= 0; i--) {
      alert( arr[i] );
    }
  }
  
  printReverseList(list);

Rest参数/Spread语法