递归 or 循环？！

递归 or 循环？！

 

      递归和循环是两个相似的方法，在初次使用中，常常不容易分辨清楚，导致很多人不敢轻易使用。关于我对这两个东东的一点点总结，如下:

 

一. 递归

 

百度上的定义：

　　程序调用自身的编程技巧称为递归（recursion）。

　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

　　注意：

　　(1) 递归就是在过程或函数里调用自身;

 　 *(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

 

用于解决三类问题：

　　(1)数据的定义是按递归定义的。(Fibonacci函数)(例2)

　　(2)问题解法按递归算法实现。(回溯) (例3)

　　(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)

 

递归的优缺点：

        优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的话，否则你更晕） 

        缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理，比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。 

 

个人观点

        递归的运用主要是把大而且重复的操作用不断调用自己的方法来实现减少代码量的目的。虽然代码减少，但是可读性也随之降低。递归中，最重要的就是递归的退出条件，没有退出条件的递归就是死递归。掌握好每个递归的退出条件，才能更好的使用递归。

 

二. 循环

 

百度上的定义：

        一组被重复执行的语句称之为循环体,能否继续重复,决定循环的终止条件。循环语句是由循环体及循环的终止条件两部分组成的。

        要使用循环语句时，必须要确定循环体及条件（布尔表达式）两个重要因素，亦即首要考虑的是：我要重复执行哪些语句，我要重复到什么时候为止！

 

循环的优缺点：

        优点：速度快，结构简单。
        缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
 

与递归的比较：

        他们的不同点在于：递归是调用自己本身，而循环是不断执行循环体。递归效率低。

        他们的共同点在于：都有结束条件，化繁为简。

      *如例1中，其中num在递归中只能到6000左右就会报栈溢出的错误，而在循环中却没有限制。

 

 

三. 实例

1. 叠加

import java.awt.Graphics;
import java.util.Calendar;
import java.util.GregorianCalendar;
import javax.swing.JFrame;

public class compare{
	public static long summey;

	/**
	 * 递归和循环的对比
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// 开始
		Calendar calendar = new GregorianCalendar();
		long start = calendar.getTimeInMillis();
		// 实验体
		recursion(6000);
		// 结束
		Calendar calendar1 = new GregorianCalendar();
		long end = calendar1.getTimeInMillis();
		long b = end - start;
		System.out.println("运行时间: " + b);
	}

	/**
	 * 循环
	 * 
	 * @param num：传入的数
	 * @return：总数
	 */
	public static long circle(long num) {
		long sum = 1;
		for (long i = 1; i <= num; i++) {
			sum = sum + i;
		}
		return sum;
	}

	/**
	 * 递归
	 * 
	 * @param num：传入的数
	 * @return:总数
	 */
	public static long recursion(long num) {
		if (num == 1)
			return 1;
		else {
			summey = num + recursion(num - 1);
		}
		return summey;
	}
}

 

  2. Fibonacci函数

public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
}

 

   3. Hanoi问题

package Hanoi;

import java.io.*;

public class Hanoi {
	/**
	 * 主类
	 * 
	 * @param args
	 * @throws IOException
	 */
	public static void main(String args[]) throws IOException {
		Hanoi ha = new Hanoi();
		ha.go();
	}
	/**
	 * 运行的方法
	 * 
	 * @throws IOException
	 */
	public void go() throws IOException {
		int n;
		// 创建一个输入流，将接收到的数字作为要用的数
		BufferedReader buf;
		buf = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("请输入盘数：");
		n = Integer.parseInt(buf.readLine());
		Hanoi hanoi = new Hanoi();
		hanoi.move(n, 'A', 'B', 'C');
	}
	/**
	 * 移动
	 * @param n：总个数
	 * @param a：形参指A盘
	 * @param b：形参指B盘
	 * @param c：形参指C盘
	 */
	public void move(int n, char a, char b, char c) {
		if (n == 1) {
			System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
		} else {
			move(n - 1, a, c, b);
			System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
			move(n - 1, b, a, c);
		}
	}
}