Java中遞歸的作用是什么

這篇文章主要介紹“Java中遞歸的作用是什么”，在日常操作中，相信很多人在Java中遞歸的作用是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java中遞歸的作用是什么”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

概念

簡單地說:遞歸就是方法自己調(diào)用自己,每次調(diào)用時傳入不同的變量.遞歸有助于編程者解決復(fù)雜的問題,同時可以讓代碼變得整潔.

遞歸能解決什么樣的問題

1. 各種數(shù)學(xué)問題如:八皇后問題,漢諾塔,階乘問題,迷宮問題,球和籃子問題(google編程大賽).

2. 各種算法中也會用到遞歸,比如快排,歸并排序,二分查找,分治算法等.

3. 將用棧解決的問題->遞歸代碼比較簡潔.

遞歸需要遵守的規(guī)則

1. 執(zhí)行一個方法時,就創(chuàng)建一個新的受保護(hù)的獨(dú)立空間(?？臻g).

2. 方法的局部變量是獨(dú)立的,不會相互影響.

3. 如果方法中使用的變量是引用類型的變量(比如數(shù)組),就會共享該引用類型的數(shù)據(jù).

4. 遞歸必須向退出遞歸的條件逼近,否則就是無限遞歸.

5. 當(dāng)一個方法執(zhí)行完畢,或者遇到return,就會返回,遵守誰調(diào)用就將結(jié)果返回給誰,同時當(dāng)方法執(zhí)行完畢或者返回時,該方法也就執(zhí)行完畢.

遞歸回溯解決迷宮問題

在一個二維數(shù)組中,1表示墻,求小球從指定點(diǎn)到終點(diǎn)走過的路徑.

package com.structures.recursion;  public class MiGong {     public static void main(String[] args) {         //先創(chuàng)建二維數(shù)組模擬迷宮,地圖         int[][] map = new int[8][7];         //使用1表示墻,迷宮的上下左右邊全部置為1         for (int i = 0; i < 7; i++) {             map[0][i] = 1;             map[7][i] = 1;         }         for (int i = 0; i < 8; i++) {             map[i][0] = 1;             map[i][6] = 1;         }         //設(shè)置擋板         map[3][1] = 1;         map[3][2] = 1;         //輸出地圖         System.out.println("原始地圖");         for (int i = 0; i < 8; i++) {             for (int j = 0; j < 7; j++) {                 System.out.print(map[i][j] + " ");             }             System.out.println();         }          //使用遞歸回溯找路         setWay(map, 1, 1);         System.out.println("按策略走過的路");         for (int i = 0; i < 8; i++) {             for (int j = 0; j < 7; j++) {                 System.out.print(map[i][j] + " ");             }             System.out.println();         }          /*         原始地圖         1 1 1 1 1 1 1         1 0 0 0 0 0 1         1 0 0 0 0 0 1         1 1 1 0 0 0 1         1 0 0 0 0 0 1         1 0 0 0 0 0 1         1 0 0 0 0 0 1         1 1 1 1 1 1 1         按策略走過的路         1 1 1 1 1 1 1         1 2 0 0 0 0 1         1 2 2 2 0 0 1         1 1 1 2 0 0 1         1 0 0 2 0 0 1         1 0 0 2 0 0 1         1 0 0 2 2 2 1         1 1 1 1 1 1 1          */     }      /**      * 使用遞歸回溯來找路,如果能map[6][5]位置,則說明通路找到      * 約定:當(dāng)map[i][j]為0表示該點(diǎn)沒有走過,當(dāng)為1表示墻,當(dāng)為2表示通路可以走,3表示該點(diǎn)已經(jīng)走過,但是走不通      * 在走迷宮時,需要確定一個策略(方法),下->右->上->左,如果走不通再回溯      *      * @param map 表示地圖      * @param i   從哪個位置開始行坐標(biāo)      * @param j   從哪個位置開始列坐標(biāo)      * @return 如果找到通路, 就返回true, 否則返回false      */     public static boolean setWay(int[][] map, int i, int j) {         if (map[6][5] == 2) {             return true;         } else {             if (map[i][j] == 0) {//如果當(dāng)前這個點(diǎn)沒有走過                 //按照策略下->右->上->左 走                 map[i][j] = 2;//假定該點(diǎn)可以走通                 if (setWay(map, i + 1, j)) {//向下走                     return true;                 } else if (setWay(map, i, j + 1)) {//向右走                     return true;                 } else if (setWay(map, i - 1, j)) {//向上走                     return true;                 } else if (setWay(map, i, j - 1)) {//向左走                     return true;                 } else {                     map[i][j] = 3;//說明該點(diǎn)是死路,走不通                     return false;                 }             } else {                 //如果map[i][j] != 0,說明可能是1,2,3                 return false;             }         }     } }

八皇后問題

在8*8的國際象棋上擺放8個皇后,使其不能相互攻擊,即:任意兩個皇后都不能處于同一行,同一列,同一斜線上,問有多少種擺法.

理論上應(yīng)該創(chuàng)建一個二維數(shù)組來表示棋盤,但是實(shí)際上可以通過算法,用一個一維數(shù)組即可解決問題,arr[8]={0,4,7,5,2,6,1,3},對應(yīng)arr下標(biāo)表示第幾行,即第幾個皇后,arr[i]=val,val表示第i+1個皇后,放在第i+i行的val+1列.

package com.structures.recursion;  public class Queen8 {     //表示共有多少個皇后     private int max = 8;     //定義數(shù)組array,保存皇后放置位置的結(jié)果,比如arr[8]={0,4,7,5,2,6,1,3}     private int[] array = new int[max];      static int count = 0;      public static void main(String[] args) {         Queen8 queen8 = new Queen8();         queen8.check(0);         System.out.printf("總共%d擺法\n",count);//92種     }      //放置第n個皇后     public void check(int n) {         if (n == max) {//n=8 說明前面已經(jīng)放好             print();             count++;             return;         }         //依次放入皇后并判斷是否沖突         for (int i = 0; i < max; i++) {             //先把當(dāng)前的皇后n,放到改行的第1列             array[n] = i;             //判斷當(dāng)放置第n個皇后到第i列是,是否沖突.             if (judge(n)) {                 //接著放n+1皇后,開始遞歸                 check(n + 1);             }         }     }      //查看當(dāng)放置第n個皇后時,就去檢測該皇后是否前面已經(jīng)擺放的皇后沖突     private boolean judge(int n) {         for (int i = 0; i < n; i++) {             //array[i] == array[n] 表示第n個皇后是否與之前的皇后在同一列             //Math.abs(n - i) == Math.abs(array[n] - array[i]) 表示第n個皇后是否與之前在同一個斜線             if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {                 return false;             }         }         return true;     }      //將皇后擺放的位置輸出     public void print() {         for (int i = 0; i < array.length; i++) {             System.out.print(array[i] + " ");         }         System.out.println();     } }

到此，關(guān)于“Java中遞歸的作用是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！