现在的位置: 首页 > 综合 > 正文

递归问题

2013年03月19日 ⁄ 综合 ⁄ 共 8123字 ⁄ 字号 小 中 大 ⁄ 评论关闭

 

转自：http://blog.csdn.net/justinavril/archive/2008/08/01/2753596.aspx

 

所谓递归问题，可以分成两部分来理解：一是基本问题，也可以称之为原始问题，比较好解决；二是后续问题，比较复杂，但是和原始问题比较类似，可以调用自身的一个新的副本去解决它。

最简单的可以归为递归问题的就是阶乘，1的阶乘我们知道是1，2的阶乘为2*1=2*1!，而3的阶乘又是3*2!...这样我们就能够知道如何用递归去实现n的阶乘了。

 

view plaincopy to clipboardprint?
  1. public class Factorial {  
  2.    public static int factorial (int n){  
  3.     int result = 0;  
  4.           
  5.     if (n <= 1){  
  6.         result = 1;  
  7.     }  
  8.     else if (n > 1){  
  9.         result = n * factorial (n-1);  
  10.     }  
  11.     return result;  
  12.    }  
  13.       
  14.    public static void main (String args[]){  
  15.     for (int i=0; i<10; i++)  
  16.         System.out.print(factorial (i) +" ");  
  17.    }  
  18. }  

 

输出：

 

view plaincopy to clipboardprint?
  1. 1 1 2 6 24 120 720 5040 40320 362880  

 

当然了这是最简单的，也是最好理解的递归例子，但是它揭示了递归的实质：将复杂问题递归为简单问题解决...

我们再来看看稍微复杂点的，也比较有意思，汉诺塔问题：有1，2，3这3个柱子，1号柱子上有n个盘子（盘子由小到大地串在上面，且小盘子永远不能在大盘子下面），以2号柱子为临时存放地，最终将n个盘子移到3号柱子上。将这个问题分析为递归问题，分解出以下三点：

1. 从1号柱子移动n-1个盘子到2号柱子，3号柱子为临时存放点；

2. 从1号柱子将第n个盘子移到3号柱子；

3. 将n-1个柱子从2号柱子移到3号柱子，1号柱子为临时存放点。

请看代码：

 

view plaincopy to clipboardprint?
  1. public class Hanoi {  
  2.    public static void hanoi (int movingPans, String sourcePillar, String targetPillar, String tempPillar){  
  3.     if (movingPans == 1){  
  4.         movePans (1, sourcePillar, targetPillar);   
  5.     }  
  6.     else{  
  7.         hanoi(movingPans-1, sourcePillar, tempPillar, targetPillar);  
  8.         movePans (movingPans, sourcePillar, targetPillar);  
  9.         hanoi(movingPans-1, tempPillar, targetPillar, sourcePillar);  
  10.     }     
  11.    }  
  12.       
  13.    public static void movePans (int panNum, String sourcePillar, String targetPillar){  
  14.     System.out.println("Move "+ panNum +" form "+ sourcePillar +"# to "+ targetPillar +"#");  
  15.    }  
  16.       
  17.    public static void main(String args[]){  
  18.     System.out.println("3个盘子的汉诺塔问题：");  
  19.     hanoi(3, "1", "3", "2");  
  20.     System.out.println("5个盘子的汉诺塔问题：");  
  21.     hanoi(5, "1", "3", "2");  
  22.    }  
  23. }  

 

输出：

 

view plaincopy to clipboardprint?
  1. 3个盘子的汉诺塔问题：  
  2. Move 1 form 1# to 3#  
  3. Move 2 form 1# to 2#  
  4. Move 1 form 3# to 2#  
  5. Move 3 form 1# to 3#  
  6. Move 1 form 2# to 1#  
  7. Move 2 form 2# to 3#  
  8. Move 1 form 1# to 3#  
  9. 5个盘子的汉诺塔问题：  
  10. Move 1 form 1# to 3#  
  11. Move 2 form 1# to 2#  
  12. Move 1 form 3# to 2#  
  13. Move 3 form 1# to 3#  
  14. Move 1 form 2# to 1#  
  15. Move 2 form 2# to 3#  
  16. Move 1 form 1# to 3#  
  17. Move 4 form 1# to 2#  
  18. Move 1 form 3# to 2#  
  19. Move 2 form 3# to 1#  
  20. Move 1 form 2# to 1#  
  21. Move 3 form 3# to 2#  
  22. Move 1 form 1# to 3#  
  23. Move 2 form 1# to 2#  
  24. Move 1 form 3# to 2#  
  25. Move 5 form 1# to 3#  
  26. Move 1 form 2# to 1#  
  27. Move 2 form 2# to 3#  
  28. Move 1 form 1# to 3#  
  29. Move 3 form 2# to 1#  
  30. Move 1 form 3# to 2#  
  31. Move 2 form 3# to 1#  
  32. Move 1 form 2# to 1#  
  33. Move 4 form 2# to 3#  
  34. Move 1 form 1# to 3#  
  35. Move 2 form 1# to 2#  
  36. Move 1 form 3# to 2#  
  37. Move 3 form 1# to 3#  
  38. Move 1 form 2# to 1#  
  39. Move 2 form 2# to 3#  
  40. Move 1 form 1# to 3#  

 

 

 

在前文《递归问题一》中简单介绍了几个典型的递归问题。前几天看到一个人在论坛里问，如何实现一个字符串数组的全排列问题，底下人都说可以用递归方法实现，我想了会，没想出来，不过有人贴出了他的代码，我这里借用一下：

 

view plaincopy to clipboardprint?
  1. public class AllSort{   
  2.     public static void main(String[] args) {   
  3.         char buf[]={'a','b','c'};   
  4.   
  5.         perm(buf,0,buf.length-1);   
  6.     }   
  7.     public static void perm(char[] buf,int start,int end){   
  8.         if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可    
  9.             for(int i=0;i<=end;i++){   
  10.                 System.out.print(buf[i]);   
  11.             }   
  12.             System.out.println();      
  13.         }   
  14.         else{//多个字母全排列    
  15.             for(int i=start;i<=end;i++){   
  16.                 char temp=buf[start];//交换数组第一个元素与后续的元素    
  17.                 buf[start]=buf[i];   
  18.                 buf[i]=temp;   
  19.                    
  20.                 perm(buf,start+1,end);//后续元素递归全排列    
  21.                    
  22.                 temp=buf[start];//将交换后的数组还原    
  23.                 buf[start]=buf[i];   
  24.                 buf[i]=temp;   
  25.             }   
  26.         }   
  27.     }   
  28. }  

 

输出：

 

view plaincopy to clipboardprint?
  1. abc  
  2. acb  
  3. bac  
  4. bca  
  5. cba  
  6. cab  

 

还有一个比较著名的递归问题，就是n皇后问题。就是在一个n*n的国际象棋的方格中，怎么样才能将n个皇后摆在棋盘上共存。我们知道皇后是能横着，竖着和对角线这样三条路子。以8皇后为例讨论这个问题，那么为了和Java中的数组第一个索引0更好的结合起来，我们定义8*8的棋盘中每个方格的坐标为(0, 0)，(0, 1)...假定两个皇后(i, j)，(k, l)，那么这两个皇后的坐标一定得满足：(i != k) && (j != l) && (|i-k| != |j-l|)。我们以一个长度为8的数组表示皇后的坐标，例如(0, 1, 2, ... , 7)，这就意味着第一个皇后摆在(0, 0)上，第二个皇后在(1, 1)上，依次类推。这样就能保证每个皇后的纵坐标是不一样的。下面是具体的实现代码：

 

view plaincopy to clipboardprint?
  1. class NQueen{  
  2.     private int noOfSolutions;  
  3.     private int noOfQueens;  
  4.     private int[] queensInRow;  
  5.       
  6.     public NQueen (){  
  7.         this.noOfQueens = 8;  
  8.         this.queensInRow = new int[8];  
  9.         this.noOfSolutions = 0;  
  10.     }  
  11.       
  12.     public NQueen (int queens){  
  13.         this.noOfQueens = queens;  
  14.         this.queensInRow = new int[noOfQueens];  
  15.         this.noOfSolutions = 0;  
  16.     }  
  17.       
  18.     public boolean canPlaceQueen (int k, int i){  
  19.         for (int j=0; j<k; j++){  
  20.             if ((queensInRow[j]==i) || (Math.abs(queensInRow[j]-i)== Math.abs(j-k))){  
  21.                 return false;  
  22.             }  
  23.         }  
  24.         return true;  
  25.     }  
  26.       
  27.     public void queensConfiguration (int k){  
  28.         for (int i=0; i<noOfQueens; i++){  
  29.             if (canPlaceQueen(k, i)){  
  30.                 queensInRow[k] = i;  
  31.                   
  32.                 if (k == noOfQueens-1){  
  33.                     printConfiguration();  
  34.                 }  
  35.                 else{  
  36.                     queensConfiguration(k+1);  
  37.                 }  
  38.             }  
  39.         }  
  40.     }  
  41.       
  42.     public void printConfiguration (){  
  43.         noOfSolutions ++;  
  44.         System.out.print("(");  
  45.           
  46.         for (int i=0; i<noOfQueens-1; i++){  
  47.             System.out.print(queensInRow[i] +", ");  
  48.         }  
  49.         System.out.println(queensInRow[noOfQueens-1] +")");  
  50.     }  
  51.       
  52.     public int solutionsCount(){  
  53.         return noOfSolutions;  
  54.     }  
  55. }  
  56. public class TestNQueen {  
  57.     public static void main (String args[]){  
  58.         NQueen queen = new NQueen();  
  59.           
  60.         queen.queensConfiguration(0);  
  61.     }  
  62. }  

 

输出：

 

view plaincopy to clipboardprint?
  1. (0, 4, 7, 5, 2, 6, 1, 3)  
  2. (0, 5, 7, 2, 6, 3, 1, 4)  
  3. (0, 6, 3, 5, 7, 1, 4, 2)  
  4. (0, 6, 4, 7, 1, 3, 5, 2)  
  5. (1, 3, 5, 7, 2, 0, 6, 4)  
  6. (1, 4, 6, 0, 2, 7, 5, 3)  
  7. (1, 4, 6, 3, 0, 7, 5, 2)  
  8. (1, 5, 0, 6, 3, 7, 2, 4)  
  9. (1, 5, 7, 2, 0, 3, 6, 4)  
  10. (1, 6, 2, 5, 7, 4, 0, 3)  
  11. (1, 6, 4, 7, 0, 3, 5, 2)  
  12. (1, 7, 5, 0, 2, 4, 6, 3)  
  13. (2, 0, 6, 4, 7, 1, 3, 5)  
  14. (2, 4, 1, 7, 0, 6, 3, 5)  
  15. (2, 4, 1, 7, 5, 3, 6, 0)  
  16. (2, 4, 6, 0, 3, 1, 7, 5)  
  17. (2, 4, 7, 3, 0, 6, 1, 5)  
  18. (2, 5, 1, 4, 7, 0, 6, 3)  
  19. (2, 5, 1, 6, 0, 3, 7, 4)  
  20. (2, 5, 1, 6, 4, 0, 7, 3)  
  21. (2, 5, 3, 0, 7, 4, 6, 1)  
  22. (2, 5, 3, 1, 7, 4, 6, 0)  
  23. (2, 5, 7, 0, 3, 6, 4, 1)  
  24. (2, 5, 7, 0, 4, 6, 1, 3)  
  25. (2, 5, 7, 1, 3, 0, 6, 4)  
  26. (2, 6, 1, 7, 4, 0, 3, 5)  
  27. (2, 6, 1, 7, 5, 3, 0, 4)  
  28. (2, 7, 3, 6, 0, 5, 1, 4)  
  29. (3, 0, 4, 7, 1, 6, 2, 5)  
  30. (3, 0, 4, 7, 5, 2, 6, 1)  
  31. (3, 1, 4, 7, 5, 0, 2, 6)  
  32. (3, 1, 6, 2, 5, 7, 0, 4)  
  33. (3, 1, 6, 2, 5, 7, 4, 0)  
  34. (3, 1, 6, 4, 0, 7, 5, 2)  
  35. (3, 1, 7, 4, 6, 0, 2, 5)  
  36. (3, 1, 7, 5, 0, 2, 4, 6)  
  37. (3, 5, 0, 4, 1, 7, 2, 6)  
  38. (3, 5, 7, 1, 6, 0, 2, 4)  
  39. (3, 5, 7, 2, 0, 6, 4, 1)  
  40. (3, 6, 0, 7, 4, 1, 5, 2)  
  41. (3, 6, 2, 7, 1, 4, 0, 5)  
  42. (3, 6, 4, 1, 5, 0, 2, 7)  
  43. (3, 6, 4, 2, 0, 5, 7, 1)  
  44. (3, 7, 0, 2, 5, 1, 6, 4)  
  45. (3, 7, 0, 4, 6, 1, 5, 2)  
  46. (3, 7, 4, 2, 0, 6, 1, 5)  
  47. (4, 0, 3, 5, 7, 1, 6, 2)  
  48. (4, 0, 7, 3, 1, 6, 2, 5)  
  49. (4, 0, 7, 5, 2, 6, 1, 3)  
  50. (4, 1, 3, 5, 7, 2, 0, 6)  
  51. (4, 1, 3, 6, 2, 7, 5, 0)  
  52. (4, 1, 5, 0, 6, 3, 7, 2)  
  53. (4, 1, 7, 0, 3, 6, 2, 5)  
  54. (4, 2, 0, 5, 7, 1, 3, 6)  
  55. (4, 2, 0, 6, 1, 7, 5, 3)  
  56. (4, 2, 7, 3, 6, 0, 5, 1)  
  57. (4, 6, 0, 2, 7, 5, 3, 1)  
  58. (4, 6, 0, 3, 1, 7, 5, 2)  
  59. (4, 6, 1, 3, 7, 0, 2, 5)  
  60. (4, 6, 1, 5, 2, 0, 3, 7)  
  61. (4, 6, 1, 5, 2, 0, 7, 3)  
  62. (4, 6, 3, 0, 2, 7, 5, 1)  
  63. (4, 7, 3, 0, 2, 5, 1, 6)  
  64. (4, 7, 3, 0, 6, 1, 5, 2)  
  65. (5, 0, 4, 1, 7, 2, 6, 3)  
  66. (5, 1, 6, 0, 2, 4, 7, 3)  
  67. (5, 1, 6, 0, 3, 7, 4, 2)  
  68. (5, 2, 0, 6, 4, 7, 1, 3)  
  69. (5, 2, 0, 7, 3, 1, 6, 4)  
  70. (5, 2, 0, 7, 4, 1, 3, 6)  
  71. (5, 2, 4, 6, 0, 3, 1, 7)  
  72. (5, 2, 4, 7, 0, 3, 1, 6)  
  73. (5, 2, 6, 1, 3, 7, 0, 4)  
  74. (5, 2, 6, 1, 7, 4, 0, 3)  
  75. (5, 2, 6, 3, 0, 7, 1, 4)  
  76. (5, 3, 0, 4, 7, 1, 6, 2)  
  77. (5, 3, 1, 7, 4, 6, 0, 2)  
  78. (5, 3, 6, 0, 2, 4, 1, 7)  
  79. (5, 3, 6, 0, 7, 1, 4, 2)  
  80. (5, 7, 1, 3, 0, 6, 4, 2)  
  81. (6, 0, 2, 7, 5, 3, 1, 4)  
  82. (6, 1, 3, 0, 7, 4, 2, 5)  
  83. (6, 1, 5, 2, 0, 3, 7, 4)  
  84. (6, 2, 0, 5, 7, 4, 1, 3)  
  85. (6, 2, 7, 1, 4, 0, 5, 3)  
  86. (6, 3, 1, 4, 7, 0, 2, 5)  
  87. (6, 3, 1, 7, 5, 0, 2, 4)  
  88. (6, 4, 2, 0, 5, 7, 1, 3)  
  89. (7, 1, 
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞