介绍:
你用你手中的钥匙打开一扇门, 结果去发现前方还有一扇门, 紧接着你又用钥匙打开了这扇门, 然后你又看到一扇门...... 但是当你开到一扇门时, 发现前方是一堵墙无路可走了, 你选择原路返回 -- 这就是递归.
但是如果你打开一扇门后, 同样发现前方也有一扇门, 紧接着你又打开下一扇门..... 但是却一直没有碰到尽头 -- 这就是循环.
简单来说: 循环是有去无回, 而递归是有去有回 (因为存在终止条件).
循环: 当满足某一条件时反复执行某一操作 (循环体).
递归: 在一个方法内部对自身进行调用的方法.
递归结构包括两个部分:
1, 递归头: 即什么时候不调用自身方法, 也就是递归的结束条件. 如果没有递归头, 程序将陷入死循环.
2, 递归体: 即什么时候需要调用自身方法.
好了, 废话不多说, 直接来撸代码 (计算阶乘的方法).
- package com.bjwyj.method;
- /**
- * 递归和循环的比较
- * @author 吴永吉
- *
- */
- public class TestRecursion {
- public static void main(String[] args) {
- // 以下调用 System 下的 currentTimeMillis() 方法只是为了说明递归调用比循环调用更耗时
- long l1 = System.currentTimeMillis();
- System.out.println(factorial(5));
- long l2 = System.currentTimeMillis();
- System.out.println("递归计算阶乘耗时:"+(l2-l1));
- System.out.println("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$");
- long time1 = System.currentTimeMillis();
- System.out.println(factorialLoop(5));
- long time2 = System.currentTimeMillis();
- System.out.println("循环计算阶乘耗时:"+(time2-time1));
- }
- // 使用递归定义计算阶乘的方法
- public static long factorial(int num) {
- if(num==1) { // 递归头
- return 1;
- }else {
- return num*factorial(num-1); // 递归体
- }
- }
- // 使用循环定义计算阶乘的方法
- public static long factorialLoop(int n) {
- int result = 1; // 接收计算结果
- while(n>1) {
- result *= n*(n-1); // 实现计算结果的累乘操作
- n -= 2; // 每次减去 2, 实现数字的迭代操作
- }
- return result;
- }
- }
执行结果:
120
递归计算阶乘耗时: 1
- $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
- 120
循环计算阶乘耗时: 0
由结果可以看出, 使用递归算法比使用循环算法更耗时.
为了更好地比较递归算法的优劣, 上述采用 while 循环与递归算法进行对比.
先来分析上述递归方法的执行过程, 如下图:
循环方法的执行过程, 如下图:
这里为了看起来清晰, 只是简单地画出了栈内存中的执行过程 (这样画更便于理解).
总结:
栈, 主要是用来存放栈帧的, 每执行一个方法就会出现压栈操作, 所以采用递归的时候产生的栈帧比较多, 递归就会影响到内存, 非常消耗内存. 而使用循环就执行了一个方法, 压入栈帧一次, 只存在一个栈帧, 所以比较节省内存.
来源: https://www.cnblogs.com/wuyongji/p/10503391.html