数据结构之递归算法

首先通过两个小案例来认识一下递归

package com.gcy.recursion;

import com.gcy.linkedlist.TestStack;

/**
* 简单回顾递归调用
* @author Administrator
*
*/
public class RecursionTest {

public static void main(String[] args) {
//理解其打印顺序应该为2,3,4,5,6,7
test(7);
//阶乘问题,计算4的阶乘
int result=factorial(4);
System.out.println("4的阶乘为："+result);

}
//打印问题
public static void test(int n) {
if(n>2) {
test(n-1);
}
System.out.println(n);
}
//阶乘问题
public static int factorial(int n ) {
if(n==1) {
return 1;
}else {
return factorial(n-1)*n;
}
}

}

递归可以解决的问题：

1.数学问题：八皇后问题、汉诺塔问题，阶乘，迷宫问题，球和篮子等

2.各种算法中国也会使用到：快速排序，归并排序、二分查找、分治算法

递归需要遵守的重要规则

1.在执行额一个方法时，创建一个新的受保护的独立空间（栈空间）

2.方法的局部变量时独立的，不会互相影响

3.递归必须向递归的条件接近，否则会发生无限递归

4.当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果放回给谁，同时当方法执行完毕或者返回时，该方法就执行完毕