递归和call stack

一、 递归的写法套路

斐波那契数列

形如 1,1,2,3,5,8,13,21,34......这样的数列，某个位置的数字等于它前面两项数字的和
求斐波那契数列第 n 项的值的代码如下：

function fib(n){
  if(n ===1 || n === 2){
    return 1
  } else{
    return fib(n-1) + fib(n-2)
  }
}
console.log(fib(6))  // 8

结果证明是对的

求阶乘

代码如下

function fac(n){
  if(n ===1 || n === 0){
    return 1
  } else{
    return n * fac(n-1)
  }
}
console.log(fac(5)) // 120

套路如下

1. 找规律：找用一个公式可以总结出的规律
   像递归的规律比较好找，等于前两项的和就行了，而且用公式也比较好表达
   但是阶乘的常见的规律不是比较好用公司来总结，因为它是等于前 n 项的的乘积
   但是他还有一个通式 是 百度可得

   
   
   image.png
   
   

   明显第二个可以用公式表达出来

2. 找出口：整个数列会有一个确定的值，其他的值都是根据这个值和规律算出来的
3. 像上面一样写if ...else ...

二、 call stack

stack是栈的意思，看上面的函数的执行过程，实际上每一次运算，前面的所有的值都在“等着后面的结果”，每当函数运行一次，都会call stack一下，而且因为stack 是遵循先入后出的，就是最先进去的运算（或者过程）最后出来，当需要算的值比较大的时候，stack 里面的位置就可能会不够用，就会出现错误。
因此，一般不要用 递归来进行计算，而且一般的递归都可以用循环来解决

有机会会更新一下用循环的写法来进行上面的运算