js尾递归函数

时间:2021-08-27 02:43:14

 

普通递归:

function fac(n) {
  if (n === 1) return 1;
  return n * fac(n - 1);
}

fac(5) // 120

这是个阶乘。但是占用内存,因为:

fac(5)

(5*fac(4))

(5*(4*fac(3)))

(5*(4*(3*fac(2))))

(5*(4*(3*(2*fac(1)))))

(5*(4*(3*2)))

(5*(4*(6)))

(5*24)

120

这里需要讲明的是: 函数调用会产生“调用记录(存储着函数的相关信息)”存放在栈中,当有函数返回,对应的调用记录才会消失,

         上述用普通递归实现的阶乘的执行过程中,不断的调用自身,导致一直没有返回,这样也就不断的在栈中存储调用记录

         而当调用自身的次数过多后,就会产生我们常说的“栈溢出”

拟人描述: 就想一个人不断地借钱(调用自身,不断向栈中存调用记录),但是总想着以后再还(一直没有返回),

     当外债积累到超出自己偿还能力的时候,就跑路了(栈溢出)

 

尾递归

function fac(n, total) {
  if (n === 1) return total;
  return fac(n - 1, n * total);
}

fac(5, 1) // 120

执行过程如下:

fac(5,1)

fac(4,5)

fac(3,20)

fac(2,60)

fac(1,120)

说明:永远只有一个调用记录,调用函数产生一个调用记录,最后一步操作 return fac(n - 1, n * total) 

   把当前函数的计算结果当做参数传递给了下一个自身调用,这样第一个函数调用产生的调用记录就消失了,因为它执行完了

   依次类推,就不会溢出

尾递归:函数的最后一步是执行一个函数

参考来自:阮老师