耿老师带你深入Java学习：掌握递归与迭代的精髓

耿老师寄语

本文通过大家熟悉的Fibonacci序列 ，描述用“迭代法”求解Fibonacci序列更容易被理解，而用“递归”求解（不同于通常教材的递归算法，但效率更高）更难理解php递归算法。

神理解递归php递归算法，人理解迭代

耿祥义

本文通过大家熟悉的Fibonacci序列（前两项都是1php递归算法，以后每项是前两项的和）

1 1 2 3 5 8 13 21 34 55 89... ...

来描述用“迭代法”求解Fibonacci序列更容易被理解，而用“递归”求解（不同于通常教材的递归算法，但效率更高）更难理解php递归算法。

1.递归和迭代的特点

"神理解递归，人理解迭代"这句话的出处已经无法查证，但本人非常赞同这句话php递归算法。递归是分治算法的最佳体现，即将规模大的算法问题分解成规模小的算法问题，最终解决规模大的算法问题。

●递归算法有两个主要特点：

（1）算法简洁

代码量很小，逻辑理解相对容易，但对于某些递归，理解算法的内部细是有相当难度的，这就是"神理解递归，人理解迭代"这句话的原因php递归算法。

（2）栈溢出（StackOverflow）

递归需要进行函数的压栈和弹栈操作，如果递归深度较大就会占用大量的栈上空间，而且压栈和弹栈都会增加算法的用时php递归算法。因此，递归算法的一个主要问题就是，当递归深度较大过大时，可能会出现栈溢出 （StackOverflow）。对于线性递归，即函数每次只递归 调用本函数一次，时间和空间复杂度都是线性级别O(n),其中n是递归深度。对于非线性递归，即函数每次递归调用本函数多于一次，时间复杂度一定是指数级别O(2^n)(2的n次幂)（空间复杂度是 线性级别O(n)），其效率会随着递归级别的增大而迅速地降低。

● 迭代算法特点

不需要进行函数的不断压栈和弹栈操作，只需保留当前计算的结果，然后计算出下一次的结果后，立刻释放当前结果php递归算法。时间复杂度和空间复杂度依赖所使用的具体算法。迭代算法通常比较凌乱，逻辑上不够简洁。

2.fibonacci序列

● 非线性递归（求Fibonacci序列第n项）

传统递归，大学教材均采用,逻辑上好理解，算法简洁，细节也相对好理解php递归算法。

展开全文

代码如下：

● 线性递归（求Fibonacci序列第n项）

非传统递归，本人未见大学教材采用，可在某些算法著作中见到线性递归求Fibonacci序列第n项php递归算法。算法简洁，但逻辑和细节-“神理解”。

代码如下：

● 迭代法（求Fibonacci序列第n项）

许多大学教材采用，算法不简洁，但有利去理解线性递归php递归算法。

代码如下：

MainClass.java

Fibonacci.java

耿祥义主要教材源代码暨习题解答下载