8

js实现递归，尾递归（递归优化），防止栈溢出

 4 years ago
source link: https://www.joynop.com/p/247.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

一 第一版一版的递归实现 n！，比如 5！= 5 * 4 * 3 * 2 *1 

let count = 9000;
const fact = (n) => {
  if (n == 1) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
};

let a = fact(count); //3628800;
console.log(a);

但这样就会保持10条记录，这样很容易造成栈溢出；我们可以这样理解，执行一个函数A，添加一个记录A，在函数A中调用函数B，添加一个记录B，等函数B执行完了之后，移除记录B，把控制器交给A。因为递归就是函数里面调用函数，所以会有10条记录。

二、尾递归

const newFact = (n) => {
  return fact_iter(n, 1);
};

const fact_iter = (num, product) => {
  if (num == 1) {
    return product;
  } else {
    return fact_iter(num - 1, num * product);
  }
};

const b = newFact(count); //3628800;

console.log(b);

这样就只保存一条记录，不会造成栈溢出。而这个为什么只有一条记录呢？这是因为函数fact_iter返回的是它本身，返回本身之后，它就不再需要控制器了(就是没它什么事了，它把任务交个了下家了)，所以不会进栈，就不会有这条记录。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK