三、递归（Recursion）

定义

递归，就是在运行的过程中调用自己

构成递归的条件：

1.子问题必须与原问题为同样的事，且更为简单

2.不能无限制的调用本身，必须有个出口，化简为非递归状况处理

基线条件和递归条件

由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。

编写程序时必须告诉它何时停止，因此每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）

示例：

//简单递归函数
	public static void cutDown(int down) {
		System.out.println(down);
		if(down<=0) {//基线条件
			return;
		}else {
			cutDown(down-1);//递归条件
		}
	}

栈

参考

定义

栈是一种只允许在一端进行插入或删除的线性表

栈的插入操作称为进栈（压栈|push）；栈删除操作称为出栈（弹栈|pop）

特点

栈就像一个杯子，我们只能从被扣放和取，所以栈中的元素是“先进后出”

Java实现

类图

状态	操作
是否栈空	压栈push
是否栈满	进栈pop

private T data[];//用数组表示栈元素
	private int maxSize;//栈空间大小
	private int top;//栈顶指针（指向栈顶）
	
	@SuppressWarnings("unchecked")
	public Stack(int maxSize) {
		this.maxSize=maxSize;
		this.data= (T[])new Object[maxSize];//定义一个泛型数组
		this.top=-1;//有的书中用的是0，但这样会占用一个内存
	}
	 //判断栈是否为空
	     public boolean isNull(){
	         boolean flag = this.top<=-1?false:true;
	         return flag;
	     }
	     
	     //判断是否栈满
	     public boolean isFull(){
	         boolean flag = this.top==this.maxSize-1?true:false;
	         return flag;
	     }
	     
	     //压栈
	     public boolean push(T vaule){
	         if(isFull()){
	             //栈满
	             return false;
	         }else{
	             data[++top] = vaule;//栈顶指针加1并赋值
	             return true;
	         }
	     }
	 
	     //弹栈
	     public T pop(){
	         if(!isNull()){
	             //栈为空
	             return null;
	         }else{
	             T value = data[top];//取出栈顶元素
	             --top;//栈顶指针-1
	             return value;
	         }
	     }

测试类：

	public static void fun(){
             //初始化栈(char类型)
             Stack<Character> stack = new Stack<Character>(10);
             
             //2状态
             System.out.println("栈是否为空："+stack.isNull());
             System.out.println("栈是否已满："+stack.isFull());
             
             //2操作
             //依次压栈
             stack.push('a');
             stack.push('b');
             stack.push('c');
             //依次弹栈
             System.out.println("弹栈顺序：");
             System.out.println(stack.pop());
             System.out.println(stack.pop());
             System.out.println(stack.pop());
         }

递归调用栈

//计算阶乘的递归函数
	public static int fact(int x) {
		if(x==1) {
			return x;
		}else {
			return x*fact(x-1);//5*4*3*2*fact(1)
		}
	}

小结：

1. 递归指的是调用自己的函数
2. 每个递归函数都有两个条件：基线条件和递归条件
3. 栈有两种操作：压栈和弹栈
4. 所有函数调用都进入栈
5. 调用栈可能很长，这将占用大量的内存