Java-递归

骑猪看日落 2022-09-10 12:21 211阅读 0赞

### 打印案例 ###

public class RE {
        
        public static void Di(int n)
        {
        
            if(n>2)
            {
        
                Di(n-1);
            }
            System.out.println("n:"+n);
        }
        public static void main(String[]args)
        {
        
            Di(4);
        }
    }
    //生成栈，然后弹栈
    输出2，3，4

### 阶乘案例 ###

public class RE {
        
        public static int Fa(int n)
        {
        
            if(n==1)return 1;
            else return Fa(n-1)*n;
        }
        public static void main(String[]args)
        {
        
            int n=Fa(3);
            System.out.println(n);
        }
    }

*  递归从栈顶到栈底的顺序进行
 *  方法的局部变量是独立的，不受影响
 *  递归一定要有退出栈的条件

### 斐波那契数列 ###

import java.util.Scanner;
    
    public class RE {
        
        public static int fiBonaci(int n){
        
            if(n==1||n==2)
            {
        
                return 1;
            }
            else{
        
                return fiBonaci(n-2)+fiBonaci(n-1);
            }
        }
        public static void main(String[]args)
        {
        
            Scanner in =new Scanner(System.in);
            int num= in.nextInt();
            System.out.println("输入"+num+"时结果为"+fiBonaci(num));
        }
    }

### 猴子吃桃问题 ###

非递归

import java.util.Scanner;
    
    public class RE {
        
        public static int GetNum(int left,int day)
        {
        
            int sum=0;
            for(int i=1;i<=day;i++)
            {
        
                sum=(left+1)*2;
                left=sum;
            }
            return sum;
        }
        public static void main(String[]args)
        {
        
            int result=GetNum(1,9);
            System.out.println(result);
        }
    }

递归式

import java.util.Scanner;
    
    public class RE {
        
        public  static int GetNum(int day)
        {
        
            if(day==10)
            {
        
                return 1;
            }
            else if(day>=1&&day<=9)
            {
        
                return (GetNum(day+1)+1)*2;
            }
            else {
        
                return -1;
            }
           
        }
        public static void main(String[]args)
        {
        
           int day=1;
           System.out.println(GetNum(day));
        }
    }

### 老鼠出迷宫问题 ###

public class MiGong {
        
    
        public static void main(String[]args)
        {
        
                int [][]map=new int [8][7];
                //0表示没有障碍物，1表示有障碍物不能走
            for(int i=0;i<7;i++)//第一行和最后一行
            {
        
                map[0][i]=1;
                map[7][i]=1;
            }
            //最左和最右的列置为1
            for(int i=0;i<8;i++)
            {
        
                map[i][0]=1;
                map[i][6]=1;
            }
            map[3][2]=1;
            map[3][1]=1;
            for(int i=0;i<map.length;i++)
            {
        
                for(int j=0;j<map[i].length;j++)
                {
        
                    System.out.print(map[i][j]+" ");
                }
                System.out.println();
            }
            T t1=new T();
            t1.find(map,1,1);
            System.out.println("\n====找路的情况如下===\n");
            for(int i=0;i<map.length;i++)
            {
        
                for(int j=0;j<map[i].length;j++)
                {
        
                    System.out.print(map[i][j]+" ");
                }
                System.out.println();
            }
        }
    }
    class T{
        
        //使用递归回溯
        public static boolean find(int[][]map,int i,int j)
        {
        
            if(map[6][5]==2)
            {
        
                return true;
            }
            else{
        
                if(map[i][j]==0)//说明可以走
                {
        
                    map[i][j]=2;//假定可以走通
                    if(find(map,i+1,j))
                    {
        
                        return true;//尝试向下走
                    }else if(find(map,i,j+1))
                    {
        
                        return true;//右
                    }
                    else if(find(map,i-1,j))
                    {
        
                        return true;//上
                    }
                    else if(find(map,i,j-1))
                    {
        
                        return true;
                    }else{
        
                        map[i][j]=3;
                        return false;
                    }
                }
                else{
        
                    return false;
                }
            }
        }
    }
    //i,j代表当前的位置，初始化的位置为（1，1）,需要规定map数组的各个值的含义
    //0代表可以走，1表示障碍物，2探测可以走的路，3表示走过，但是走不通是死路
    //当（6，5)变成2，说明找到通路，可以结束
    //确定走路的策略：下->右->上->左

*  一开始的选择会影响最终的结果

## 汉诺塔 ##

public class Hannuo {
        
    
        public static void main(String[]args)
        {
        
            tower t=new tower();
            tower.move(1,'A','B','C');
        }
    }
    class tower{
        
        public static void move(int num,char a,char b,char c)
        {
        
            if(num==1)
            {
        
                System.out.println(a+"->"+c);
            }
            else{
        
                //可以看成两个，最下面的和最上面的所有
                move(num-1,a,c,b);//借助c从a到b
                System.out.println(a+"->"+c);
                //在把b塔的所有移动到C,借助a
                move(num-1,b,a,c);
            }
        }
    }