&递归&

基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

<特点>

结构清晰，可读性强。

代码特点

结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。

<缺点>

利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成 栈溢出 的后果。

&题目A&（经典递归法解题）

求两个数的最大公约数

<>

<代码实现>

 import java.util.Scanner;
public class Main{
public static void main(String[]ages)
{
    Scanner input=new Scanner(System.in);
    int m=input.nextInt();
    int n= input.nextInt();
    god(m,n);
    System.out.println(god(m,n));
}
public static int god(int m,int n)
{
    if(m==n)
    {
        return m;
    }
    if(m>n)
    {
        return god(m-n,n);
    }
    else{
        return god(n,m);
    }
  }

}

<方法：递归方法求数位之和>

&题目B:振兴中华&

小明参加了学校的趣味运动会，其中一个项目是跳格子，地面上画着一些格子，每个格子里写一个字，如下图所示

从我做起振

我做起振兴

做起振兴中

起振兴中华

比赛是先站在左上角的写着从字的格子里，可以横向或者纵向跳到相邻的格子里，但不能跳在对角的格子里，或其他的位置，一直要跳到华字结束

要求跳过的路线刚好构成“从我做起振兴中华”这句话

请你帮助小明算一算他一共有多少种路线。

<解题方法：递归类比与深度搜索DFS>

<代码实现>

 //递归需要考虑的问题：重复，变化，边界

 import java.util.Scanner;
 public class Main {
public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    int ans=f(0,0);
    System.out.println(ans);
}
public static int f(int i,int j)
{
    if(i==3||j==4)
    {
        return 1;
    }
    else{
        return f(i+1,j)+f(i,j+1);
    }
}
  }

&题目B&<递归法计算行列式的值>

给定一个N×N的矩阵A，求|A|。

<代码实现>

 import java.util.Scanner;
  public class Main {
public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    int n= input.nextInt();
    int [][]ant=new int[n][n];
    for(int i=0;i<ant.length;i++)
    {
        for(int j=0;j<ant[i].length;j++)
        {
            ant[i][j]= input.nextInt();
        }
    }
    hls(ant);
    System.out.println(hls(ant));

}
public static int hls(int [][]ant)
{
    int res=1;
    for(int i=0;i< ant.length;i++)
    {
        for(int j=i+1;j<ant[i].length;j++)
        {
            
                int div=ant[i][i]/ant[j][i];
                for(int  k=i;k< ant.length;k++)
                {
                    ant[i][k]=ant[i][k]-div*ant[j][k];
                    int temp=ant[i][k];
                    ant[i][k]=ant[j][k];
                    ant[j][k]=temp;
                }
        }
        res=res*ant[i][i];
    }
    return res;
}

}

&题目c&

把1~n这n个整数排成一行后随机打乱顺序输出所有可能的顺序
 import java.util.Scanner;
 public class Main {
public static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    int n= input.nextInt();
    int []a=new int[n];
    boolean[]ant=new boolean[n];
    dg(a,ant,0,n);
    input.close();
    System.out.flush();
    System.out.close();
}
public static void dg(int []a,boolean[]vis,int i,int n)
{
    if(i==n)
    {
        for(int j=0;j<a.length;j++)
        {
            System.out.print(a[j]+" ");
        }
        System.out.println();
        return;
    }
    for(int j=0;j<n;j++)
    {
        if(!vis[j])
        {
            a[i]=j+1;
            vis[j]=true;
            dg(a,vis,i+1,n);//递归调用
            vis[j]=false;
        }
    }
}

}