递归

递归

什么是递归

递归就是自己调用自己，每次调用传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得更加简洁

递归执行过程

1.当程序执行到一个方法的时候，就会开辟一个新的栈
2.每个空间的局部变量是独立的

递归的案例

package recursion;

public class RecursionTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		test(5);
		System.out.printf("factorial(%d)=%d
",5,factorial(5));
	}
	
	public static void test(int n) {
		if(n>2) {
			test(n-1);
		}
		System.out.println("n="+n);
	}
	
	public static int factorial(int n) {
		if(n==1||n==0) {
			return 1;
		}else {
			return factorial(n-1)*n;
		}
	}

}

递归解决什么问题

1.8皇后、汉诺塔、阶乘、二分查找、迷宫等问题
2.快速排序、归并排序、二分查找、分治算法
3.用栈解决问题，代码整洁

递归重要的规则

1.执行一个方法会创建一个独立受到保护的栈的空间
2.方法的局部变量必须是独立的，不受到影响
3.递归方法必须与递归的条件逼近，否则无法递归
4.当一个方法结束或者遇到return，就会返回，遵循谁调用，就将结果反馈给谁，同时执行方法完毕之后或者返回的时候，该方法就执行完毕。