读《图解算法》03-递归和栈

发表于

递归

概念

  • 函数调用自己
  • 需要有基线条件和递归条件

基线条件和递归条件

每个递归函数都有两部分：基线条件和递归条件。

  • 递归条件是指函数调用自己
  • 基线条件是指函数不再调用自己，从而避免无限循环
1
2
3
4
5
6
7
8
9
10
//倒计时
function countdown(i) {
  console.log(i);
  if (i <= 0) {
    return; //基线条件
  } else {
    countdown(i - 1);
    //递归条件;
  }
}

栈

概念

  • 一种类似堆叠的盘子的数据结构

调用栈

  • 函数里面调用函数，形成一个栈结构
  • greet 里面调用 greet1 函数，计算机先为第一个函数调用分配一个内存块，再为第二个分配一个内存块（位于第一个上面），然后第二个从函数调用返回，此时栈顶的内存块被弹出，然后剩下第一个

递归调用栈

  • 特殊一点的调用栈，就是调用自己的
  • 栈中包含未完成的函数调用，这样栈就帮你跟踪了函数
  • 使用栈虽然方便，但也要付出代价，存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。