跳到主要内容

参考目录:

递归和栈帧的调用原理

阶乘

function factorial(num) {
if (num === 1) return num;
return num * factorial(num - 1); // 递归求n的阶乘,会递归n次,每次递归内部计算时间是常数,需要保存n个调用记录,复杂度 O(n)
}

const view = factorial(100);
console.time(1);
console.log(view); // 1: 3.568ms
console.timeEnd(1);

递归可能会造成栈溢出,在程序执行中,函数通过栈(stack——后进先出)这种数据实现的,每当进入一个函数 调用,栈就会增加一层栈帧,每次函数返回,栈就会减少一层栈帧。由于栈的大小不是无限的,所以,递归调用的 次数过多,就会导致栈溢出(stack overflow) 。

尾递归

// 如果改为尾递归,只需要保留一个调用记录,复杂度为O(1)
function factorial01(n, tntal) {
if (n === 1) return tntal;
return factorial(n - 1, n * tntal); // 把每一步的乘积传入到递归函数中,每次仅返回递归函数本身,total在函数调用前就会被计算,不会影响函数调用
}
console.time(2);
console.log(factorial01(5, 1)); // 120
console.timeEnd(2); // 2: 0.14404296875ms

栈帧

每一个栈帧对应着一个未运行完的函数,栈帧中保存了该函数的返回地址和局部变量。

栈帧也叫过程活动记录,是编译器用来实现过程/函数调用的一种数据结构。从逻辑上讲,栈帧就是一个函数执行 的环境:函数参数、函数的局部变量、函数执行完后返回到哪里等。

栈是从高地址向低地址延伸的。每一个函数的每次调用,都有他自己独立的一个栈帧,这个栈帧中维持着所需要 的各种信息。寄存器 ebp 指向当前栈帧的底部(高地址),寄存器 esp 指向当前的栈帧的顶部(低地址)

注意:

  • EBP 指向当前位于系统栈最上边的一个栈帧的底部,而不是系统栈的底部。严格说来,“栈帧底部”和“栈底”是不 通的概念
  • ESP 所指的是栈帧顶部和系统的顶部是同一个位置