JavaScript 用递归思想解决“斐波拉切数列”求n项值问题【详解】

用递归思想解决“斐波拉切数列”求n项值问题

任务：

斐波拉切数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 求其第 n 项

• 递推关系 : func (n) == func (n-1) + func (n - 2)
  

步骤：

1. 找规律，将这个规律转换成一个公式 return 出来。
2. 找出口，出口即终止条件，它一定是一个已知的条件。

优点:

1. 代码异常简洁。
2. 符合人类思维。

缺点：

1. 由于递归是调用函数自身，而函数调用需要消耗时间和空间：每次调用，都要在内存栈中分配空间以存储参数、临时变量、返回地址等，往栈中压入和弹出数据都需要消耗时间。这势必导致执行效率大打折扣。
2. 递归中的计算大都是重复的，其本质是把一个问题拆解成多个小问题，小问题之间存在互相重叠的部分，这样的重复计算也会导致效率的低下。
3. 调用栈可能会溢出。栈是有容量限制的，当调用层次过多，就会超出栈的容量限制，从而导致栈溢出！

总结：

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。