耿老师寄语
本文通过大家熟悉的Fibonacci序列 ，描述用“迭代法”求解Fibonacci序列更容易被理解，而用“递归”求解（不同于通常教材的递归算法，但效率更高）更难理解。
神理解递归，人理解迭代
耿祥义
本文通过大家熟悉的Fibonacci序列（前两项都是1，以后每项是前两项的和）
1 1 2 3 5 8 13 21 34 55 89... ...
来描述用“迭代法”求解Fibonacci序列更容易被理解，而用“递归”求解（不同于通常教材的递归算法，但效率更高）更难理解。
1.递归和迭代的特点
"神理解递归，人理解迭代"这句话的出处已经无法查证，但本人非常赞同这句话。递归是分治算法的最佳体现，即将规模大的算法问题分解成规模小的算法问题，最终解决规模大的算法问题。
●递归算法有两个主要特点：
（1）算法简洁
代码量很小，逻辑理解相对容易，但对于某些递归，理解算法的内部细是有相当难度的，这就是"神理解递归，人理解迭代"这句话的原因。
（2）栈溢出（StackOverflow）
递归需要进行函数的压栈和弹栈操作，如果递归深度较大就会占用大量的栈上空间，而且压栈和弹栈都会增加算法的用时。因此，递归算法的一个主要问题就是，当递归深度较大过大时，可能会出现栈溢出 （StackOverflow）。对于线性递归，即函数每次只递归 调用本函数一次，时间和空间复杂度都是线性级别O(n),其中n是递归深度。对于非线性递归，即函数每次递归调用本函数多于一次，时间复杂度一定是指数级别O(2^n)(2的n次幂)（空间复杂度是 线性级别O(n)），其效率会随着递归级别的增大而迅速地降低。
● 迭代算法特点
不需要进行函数的不断压栈和弹栈操作，只需保留当前计算的结果，然后计算出下一次的结果后，立刻释放当前结果。时间复杂度和空间复杂度依赖所使用的具体算法。迭代算法通常比较凌乱，逻辑上不够简洁。
2.fibonacci序列
● 非线性递归（求Fibonacci序列第n项）
传统递归，大学教材均采用,逻辑上好理解，算法简洁，细节也相对好理解。
展开全文
代码如下：
● 线性递归（求Fibonacci序列第n项）
非传统递归，本人未见大学教材采用，可在某些算法著作中见到线性递归求Fibonacci序列第n项。算法简洁，但逻辑和细节-“神理解”。
代码如下：
● 迭代法（求Fibonacci序列第n项）
许多大学教材采用，算法不简洁，但有利去理解线性递归。
代码如下：
MainClass.java
Fibonacci.java
耿祥义主要教材源代码暨习题解答下载
特别声明
本文仅代表作者观点，不代表本站立场，本站仅提供信息存储服务。