递归问题

• 斐波那契数列

• 求一个数的阶乘

• 一个人上台阶可以上一步也可以上两步，问他走10级台阶有多少种走法？

• 汉诺塔

• 乌龟寻路径
  。。。。。。

上诉问题都是递归调用的问题，以求阶乘为例

求数的阶乘

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

factorial(3) // 6

• 最好手动的自己在纸上写一遍这个过程，体会一下调用时，堆栈递增的过程

• 这个代码有啥问题呢，递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误(stack overflow)

• 这样不求到最后一个值是不会释放上层的堆栈的。

• 那么如何解决这个问题，目前有Tail Call Optimize尾调优化，求阶乘的代码改成

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

factorial(5, 1) // 120

• 

• 这个尾递归就不会发生堆栈溢出的问题，你体会一下两者的区别

阅读

推荐一篇阮老师的文章，希望对你理解有帮助

图片都来自网络

程序代码运行需要计算空间，就是栈，就像小学生算术需要一张演算纸一样。//这里不考虑堆，或者堆就是多那几张草稿纸。
每个子函数都需要一些局部变量，这需要在演算纸上占用空间。
程序从栈底开始计算，随着各个子函数的调用（入栈）和返回（出栈），占用的栈资源也不断的增加减少。这个过程如果能可视化，就是那个音乐节奏灯，忽闪忽闪的一会高一会儿低的 节奏灯。

栈溢出的意思就是系统分配的演算纸不够用了，你把数字写到纸外面了。
递归调用容易产生这个，是因为递归的层级是动态的，不像非递归程序， 非递归程序中存在一个最深的函数调用链，只要最深的这个链不栈溢出就可以了，而一般递归无法给出这个保证，若递归层次太深就栈溢出了。尾递归可以解决这个问题。

我也不是很懂 ，不过我的理解是 ： 上下两个水桶，上面的绿色的水，下面红色， 往上面那个水桶加入过多的水，水就会溢出到下面那个桶，把下面那个桶的一部分水挤出去，所以当你去取下面那个桶里的水的时候，水的颜色就已经变了，然后你就被老板骂了。

推荐一本书《编码》（英文名是Code），里面从二进制数，电磁继电器这些基础讲起，看了之后你就明白了
https://book.douban.com/subje...