三、递归（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实现

类图

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;//栈顶指针-1return 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. 调用栈可能很长，这将占用大量的内存