3.6 栈与递归

递归的定义

• 若一个对象部分包含它自己，或用自己给自己定义，则称这个对象是递归的。
• 若一个过程直接地或间接调用自己，则称这个过程是递归的过程。

  • 例如：递归求n的阶乘

    long Fact(long n){
      if(n==0)              // 递归函数结束条件
        	return 1;
      else
        	return n*Fact(n-1);
    }
    

• 以下三种情况常常用到递归方法
  • 递归定义的数学函数
  • 具有递归特性的数据结构
  • 可递归求解问题

1、递归定义的数学函数

• 阶乘函数
  

• 2阶Fibonaci数列：

2、具有递归性质的数据结构

• 二叉树
  

• 广义表
  A=(a,A)

3、可递归求解的问题

• 迷宫问题
• Hanoi塔问题

递归问题————用分治法求解

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

必备三个条件：
1、能将一个问题转变成一个新的问题，而新问题与原问题的解法相同或类同，不同仅是处理 对象，且这些对象是变化有规律的
2、可以通过上述转化而使问题简化
3、必须有一个明确的递归出口，或称为递归的边界

分治法求解递归问题算法的一般形式：

void p(参数表){
		if(递归结束条件)
				可直接求解步骤;————————基本项
		else
				p(较小的参数);—————————归纳项
}

函数调用过程

调用前，系统完成：

1、将实参，返回地址等传递给被调用函数
2、为被调用函数的局部变量分配存储区
3、将控制转移到被调用函数的入口

调用后，系统完成：

1、保存被调用函数的计算结果
2、释放被调用函数的数据区
3、依照被调用函数保存的返回地址将控制转移到调用函数

• 递归函数调用实现：
  • 层次
  • 递归工作栈————递归程序运行期间使用的数据存储区
  • 工作记录=》实在参数，局部变量，返回地址。
• 递归优缺点：
  优点：结构清晰，程序易读
  缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时出栈，恢复状态信息，时间复杂度比较高
• 将递归函数转换为非递归函数
  方法1：尾递归，单项递归=》循环结构
  方法2：自用栈模拟系统的运行时栈的结构

方法一：尾递归

主要思想：就是将运用递归函数的结构转换为循环结构

例题：求n的阶乘

// 首先采用递归函数的结构的情况下
long Fact(n){
  	if(n==1)     // 这里的if判断是作为递归函数出口条件
      	return 1;
  	else
      	return n*Fact(n-1);						// 这里是作为递归的循环体
}

// 然后将之转换循环结构的情况
long Fact(n){
  	long val=1;
  	// 开始循环条件
  	while(n>1){
      	val*=n;
      	--n;
    }
  	return val;
}

方法二：单项递归=》循环结构

【主要思想】虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。

long  Fib(long n){
 		if(n==1||n==2)
      	return 1;
  	else
      	return Fib(n-1)+Fib(n-2);
}

方法三：借助栈改写递归

• 递归程序在执行的需要系统提供栈来实现

• 仿照递归算法执行过程中递归工作栈的状态变换可写出相应的非递归程序

• 改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性比较差，有的还需要经过一系列优化。

• 【算法步骤】
  1、设置一个工作栈存放递归工作记录（包括实参、返回地址及局部变量等）
  2、进入非递归调用的入口（即被调用的程序开始处）将调用程序传来的实在参数和返回地址入栈（递归程序不可以作为主程序，因而可认为是被某个调用程序调用）
  3、进入递归调用的入口：当不满足递归结束条件时，逐层递归，将实参、返回地址及局部变量入栈，这一过程可用循环语句来实现——模拟递归分解过程。

• 例题：

• 【算法描述】

  public static void main(String[] args){
    System.out.println("")
  }
  
  //  首先运用递归算法将题目解出来
  public static int recursion(int n){
    	/** 算法步骤：
    			1、判断参数n是否合理
    			2、区分出递归函数边界，也就是区分递归的结束条件	
    	*/
    
    	if(n<0)
        	return error;
    	if(n==0)
        	return 1;
    	if(!=0){
        	return n*recursion(n/2);
      }else
        	return 1;
  }
  
  
  // 第二种：运用堆栈的方式来模拟递归的运行
  public static int recursion1(int n){
    	Stack<Integer> stack=new Stack<>();
    	int result=1;
    	// 利用循环结构来将每个参数值入栈
    	while(n!=0){
        stack.push(n);
        n=n/2;
      }
    	while(!stack.isEmpty())
        	result=result*stack.pop();
    	return result;
  }