JAVA 递归_java 递归 csdn

递归的思想：将大规模的问题变成小规模的问题，问题不变，规模变小
递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。
　　 循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门）。但是，入口处的人始终等不到你回去告诉他答案。
　　
1.递归的定义
递归是在函数的定义中使用函数自身的方法。
2.递归内涵？
递归就是有递去还有归来
去：递归是指递归问题可以分解为若干个规模较小，与原问题形式相同的问题，这些子问题可以用相同的解题思路来解决，就像上面的例子中的钥匙可以打开后面所有门上的锁一样；归：就是说这些问题的演化过程是一个由大到小的过程，并且会有一个明确的终点，一旦达到这个临界点，就不用往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题就得到了解决。

更直接地说，递归的基本思想就是把规模大的问题转化为规模小的子问题去解决。特别，在函数实现时，因为解决大的问题和解决小的问题往往是同一个方法，所以就产生了调用它自身的情况，这就是递归的定义所在。重要的是，解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。
3.递归三要素

• （1）、处理方法，方法自调来解决大规模的问题，提取相同的逻辑，缩小问题规模。
• （2）、明确递归的终止条件
• （3）、给出递归终止的解决办法

典型例题：

1.回文字符串的判断
使用递归的代码

//递归实现回文字符串判断  123321    abccba
public class TestDemo1{
    public static boolean isPlalindromeString(String s,int start,int end){
        if(start<end){
            if(s.charAt(start)!=s.charAt(end)){
                return false;//递归的终止条件+解决办法
            }else {//缩小问题规模，提取重复逻辑
                return isPlalindromeString(s,start+1,end-1);
            }
        }
        return true;
    }
    public static void main(String[] args){
        System.out.println(isPlalindromeString("abccba",0,5));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

循环的代码段

public class GY1 {

    //循环代替递归实现回文字符串判断
    public static boolean isPlalindromeStringByCircu(String s){
        if(s == null || s.length() == 0) return false;

        int start = 0;
        int end = s.length()-1;

        while(start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }else{
                start ++;
                end --;
            }
        }

        return true;
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.斐波那契数列



递归实现

public static long fibonacciByRecur(int n){
//        if(n == 0) return 0;
//        if(n == 1) return 1;
        if(n == 1 || n == 2)  return 1; //递归终止条件+处理办法

        //提取相同重复逻辑，来解决小规模问题
        return fibonacciByRecur(n-1)+fibonacciByRecur(n-2);
    }
    public static void main(String[] args){
        System.out.println(fibonacciByRecur(5));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

循环实现

//循环代替递归实现斐波那契数列（优化）
public class TestDemo {
    public static int Fibonacci(int n){
        if(n==1 || n==2){
            return 1;
        }
       int F1=1;
        int F2=1;
        int result = 0;
        for(int i=3;i<=n;i++){
            result = F1+F2;
            F1=F2;
            F2=result;
        }
        return result;
    }
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=5;
        int value = Fibonacci(5);
        System.out.println(value);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//优化fibonacciByRecur 使得f4,f3,f2,f1只需要计算一遍
    public static int optimizingFibonacciByRecur(int n, int first, int second){
        if(n <= 0)  return 0;

        if(n == 1){
            return first;
        }else if(n == 2){
            return second;
        }else if(n == 3){
            return first + second;
        }

        return optimizingFibonacciByRecur(n-1, second, first+second);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.阶乘n * n-1 * n-2 * … * 2 * 1
循环实现

/循环实现阶乘
    public static long factorialByCircu(int n){
        if( n < 0){
            return 0;
        }
        long result = n;
        while(n > 1){
            n--;
            result *= n;
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12

递归实现

//循环改递归实现阶乘
    public static long factorialByRecur(int n){
        if(n == 1){
            return 1;//递归终止条件+处理办法
        }
        //提取相同重复逻辑，来解决小规模问题
        return n * factorialByRecur(n-1);
    }
1
2
3
4
5
6
7
8

4.二分查找
循环实现（泛型二分查找）

 public static <E extends Comparable<E>> int binarySearch(E[] list, E key){
        if(list == null || list.length == 0){
            return -1;
        }

        int low = 0;
        int high = list.length-1;
        while(low <= high){
            int mid = (low+high)/2;// >>1
            if(key.compareTo(list[mid]) < 0){
                high = mid-1;
            }else if(key.compareTo(list[mid]) > 0){
                low = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归实现

public static int binarySearch(int[] list, int key){
        if(list == null || list.length == 0){
            return -1;
        }

        return binaySearchBrRecur(list, key, 0, list.length-1);
    }
public static int binaySearchBrRecur(int[] list, int key, int low, int high){
        if(low <= high){//提取重复逻辑，缩小问题规模
            int mid = (low+high) >> 1;
            if(list[mid] == key){
                return mid;//明确递归终止条件并给出终止条件的解决办法
            }else if(list[mid] > key){
                return binaySearchBrRecur(list, key, low, mid-1);
            }else{
                return binaySearchBrRecur(list, key, mid+1, high);
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.杨辉三角
特性：（1）0列和行列相等的位置都是1
（2）每个数字都是两肩上数字之和
i表示行，j 表示列
1）递归种植条件 j == 0 i === j
2）达到终止条件后的处理办法 return 1；
3）提取重复逻辑，缩小问题规模 Fun(i-1,j-1)+Fun(i-1,j)

//	杨辉三角
//Description:递归获取杨辉三角指定行、列(从0开始)的值
//（使用递归实现）
public class TestDemo{
    public static long PascalTriangle(int m,int n){
        if(n>m)
            return 0;
        else if(n==0 || n==m)
            return 1;
        else return PascalTriangle(m-1,n)+PascalTriangle(m-1,n-1);
    }
    public static void main(String[] args){
        System.out.println(PascalTriangle(4,1));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6.汉诺塔问题
古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。 有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下， 小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。
分析：
设最初在塔座A上的圆盘数为num，则当num=1时，只需直接将这个圆盘移到塔座C上就可以了；否则执行以下操作：
（1）用C做过度，将A柱上的（num-1）个盘子移到B上；
（2）将A柱上最后一个盘子直接移到C柱子上；
（3）用A做过度，将B上的（num-1）个盘子移到C柱子上；

递归解决三要素：
1）递归终止条件 num == 1
2)达到终止条件的解决办法 sout(“a -> c”)
3)提取重复逻辑，缩小问题规模
transfer = c
fun(num,form,transfer,to)
transfer = a
fun(num,from,transfer,to)
fun(num - 1,a,c,b)
sout(from - > to)
fun(num-1,b,a,c);

//（使用递归实现）
public class Hanoi{
    private static int count=0;
    public static void move(char A,int n,char B ){
        System.out.println("Move "+ n +" from " + A +" to " + B);
    }
    public static void Hanoi(int n,char A,char B,char C){
        count++;
        if(n==1){
            move(A,n,C);
        }else{
            Hanoi(n-1,A,C,B);
            move(A,n,C);
            Hanoi(n-1,B,A,C);
        }
    }
    public static void main(String[] arges){
        Hanoi(3,'A','B','C');
        System.out.println("总共移动了"+ count + "次");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22