首页 > 代码库 > 递归与循环
递归与循环
如果我们需要重复多次计算相同的问题，通常可以选择递归或者循环
递归的好处是代码简洁
但是递归也有明显的缺点：
- 递归是由于函数调用自身，而函数调用是需要有时间和空间的消耗的。每一函数调用，都需要在内存栈中分配空间以保存参数，返回地址和临时变量，而且往栈中压入数据和弹出数据都需要时间。
- 递归中有可能很多计算都是重复的。递归的本质是把一个大问题分解成小问题，但是多个小问题之间会有重叠的部分
- 递归可能会引发问题：调用栈溢出。
斐波拉契数列
public class Exam9_Fibonacci { public static void main(String[] args) { int n=10; //递归 long start = System.currentTimeMillis(); System.out.println("当n= "+n+" 时的结果是 "+ Fibonacci(n)); long end = System.currentTimeMillis(); System.out.println("递归方式："); System.out.println("运行的时间是"+(end-start)+"ms"); //循环 long start1 = System.currentTimeMillis(); System.out.println("\n循环方式："); Circulation(n); long end1 = System.currentTimeMillis(); System.out.println("运行的时间是"+(end1-start1)+"ms"); } //利用递归方式 private static long Fibonacci(int n) { if(n<=0) return 0; if(n==1) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } //利用循环方式 private static long Circulation(int n) { if(n<=0) return 0; if(n==1) return 1; long finSOne= 0; long finSTwo = 1; long fibN= 0; for(int i=2;i<=n;i++) { fibN = finSOne+finSTwo; finSOne = finSTwo; finSTwo = fibN; } return fibN; }}
得到的结果是：
n值 | 最终结果 | 递归方式对Fibonacci（） | 递归方法时间(ms) | 循环方法(ms) |
10 | 55 | 177 | 1 | 0 |
20 | 6765 | 21891 | 3 | 0 |
30 | 832040 | 2692537 | 14 | 0 |
40 | 102334155 | 331160281 | 1254 | 0 |
50 | 12586269025 | 40730022147 | 150514 | 0 |
60 |
|
| 时间太长 |
|
明显的看出，时间复杂的:
递归方式是以n的指数的方式递增的
循环是O(n)
所以，对于斐波那契数列，循环的方式更好
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。