devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

回溯算法（递归）_int test(int x){return (x==1)?1:(x+test(x-1))}

作者：从前慢现在也慢 | 2024-05-18 23:51:25

赞

踩

int test(int x){return (x==1)?1:(x+test(x-1))}
递归：递归就是在函数里调用函数本身。

基线条件和递归条件
1、基线条件：就是指结束调用的条件，避免形成无限循环。
2、递归条件：就是指函数调用自己的条件。
3、递归必须向基线条件逼近，否则就会出现无线递归。

一、打印问题

给出一个整数，使用递归打印它。

  1. public class Recursion {
  2.     public static void main(String[] args) {
  3.         Recursion.test(4);
  4.     }
  5.  
  6.     public static void test(int a) {
  7.         if (a > 2) {
  8.             test(a-1);
  9.         }
  10.         System.out.println(a);
  11.     }
  12. }
  13.  
  14.  
  15. 解读：
  16. 第一次调用test，创建一个栈，传入4，判断4是否会大于2，4大于2进行第二次调用，4-1
  17. 第二次调用test，创建一个栈，传入3，判断3是否会小于2，3大于2进行第三次调用，3-1
  18. 第三从调用test，创建一个栈，传入2，判断2是否会大于2，2等于2进行返回
  19. 第一次返回，销毁栈，打印2，
  20. 第二次返回，销毁栈，打印3
  21. 第三次返回，销毁栈，打印4
  22. 结束程序
  23.  
  24. 2
  25. 3
  26. 4

二、累加问题

给出一个整数，使用递归求出它累加的和。

  1. public class Accumulation {
  2.     public static void main(String[] args) {
  3.         int a = Accumulation.test(3);
  4.         System.out.println(a);
  5.     }
  6.  
  7.     public static int test(int x) {
  8.         if (x == 1) {
  9.             return 1;
  10.         } else {
  11.             return x+test(x-1);
  12.         }
  13.     }
  14. }
  15.  
  16.  
  17. 解读：
  18. 1.在main中第一次调用test，创建第一层栈，传入3，判断是否等于1，3大于1，符合递归条件，进行第二次调用test，3-1
  19. 2.第二次调用test，创建第二层栈，传入2，判断是否等于1，2大于1，符合递归条件，进行第三次调用test，2-1
  20. 3.第三次调用test，创建第三层栈，传入1，判断是否等于1，1等于1，符合基线条件，进行返回
  21. 4.第三层栈，返回1
  22. 5.第二层栈，返回3，2+1
  23. 6.第一层栈，返回6，3+2+1
  24. 程序结束
  25.  
  26. 6

三、阶层问题
给出一个整数，使用递归求出它的阶乘。

  1. public class Factorial {
  2.     public static void main(String[] args) {
  3.         int a = Factorial.test(5);
  4.         System.out.println(a);
  5.     }
  6.  
  7.     public static int test(int x){
  8.         if (x == 1){ // 基线条件
  9.             return 1;
  10.         }else{ // 递归条件
  11.             return test(x-1) * x;
  12.         }
  13.     }
  14. }
  15.  
  16.  
  17. 递归解读：
  18.  
  19. 1. 在main中第一次调用test，创建第一层栈，传入5，判断是否等于1，5大于1，符合递归条件，进行第二次调用test，5-1
  20. 2. 第二次调用test，创建第二层栈，传入4，判断是否等于1，4大于1，符合递归条件，进行第三次调用test，4-1
  21. 3. 第三次调用test，创建第三层栈，传入3，判断是否等于1，3大于1，符合递归条件，进行第四次调用test，3-1
  22. 4. 第四次调用test，创建第四层栈，传入2，判断是否等于1，2大于1，符合递归条件，进行第五次调用test，2-1
  23. 5. 第五次调用test，创建第五层栈，传入1，判断是否等于1，1等于1，符合基线条件，进行返回
  24. 6. 第五层栈，销毁栈，返回1，return 1;
  25. 7. 第四层栈，销毁栈，返回2，return test(2-1) * 2;
  26. 8. 第三层栈，销毁栈，返回6，return test(3-1) * 3;
  27. 9. 第二层栈，销毁栈，返回24，return test(4-1) * 4;
  28. 10. 第一层栈，销毁栈，返回120，return test(24-1) * 5;
  29. 11. 程序结束
  30.  
  31. 120

四、斐波那契
用递归求出斐波那契数1,1,2,3,4,5,8,13...给一个整数x，求出它的值是多少。

  1. public class Fibonacci {
  2.     public static void main(String[] args) {
  3.         int x = 4;
  4.         int a = Fibonacci.test(x);
  5.         if (a != -1){
  6.             System.out.println("当x="+x+"，对应的斐波那契是"+a);
  7.         }
  8.     }
  9.  
  10.     //思路分析：斐波那契是前两个数之和，且必须是整数。
  11.     public static int test(int x) {
  12.         if (x >= 1) { //斐波那契必须是整数
  13.             if (x == 1 || x == 2) { //
  14.                 return 1;
  15.             } else {
  16.                 return test(x - 1) + test(x - 2);
  17.             }
  18.         } else {
  19.             System.out.println("要求输入的x必须是大于等于1的整数");
  20.             return -1;
  21.         }
  22.  
  23.     }
  24. }
  25.  
  26.  
  27. 解读：
  28. 第一次调用test方法，向方法传递整数x（x=4）
  29. 判断x是否大于等于1（因为斐波那契数不能小于1），小于1，输出提示信息，并返回-1
  30. 大于等于1，则在判断x是否是1或2，是1或2则返回1；（因为1和2的斐波那契数是1）
  31. 否则进行第二次第一个调用test，创建栈，传入3 + 第二次第二个调用test，创建栈，传入2
  32. 第二次第一个test，进行x是否大于等于1的判断，3>=1，在判断是否会等于1或2，3不等于1或2，
  33. 进行第三次第一个调用test，创建栈，传入2，+ 第三次第二个调用test，创建栈，传入1
  34. 第三次第一个test，进行x是否大于等于1的判断，2>=1，在判断是否会等于1或2，2等于1或2，进行返回
  35. 第三次第二个test，进行x是否大于等于1的判断，1>=1，在判断是否会等于1或2，1等于1或2，进行返回
  36. 第二次第二个test，进行x是否大于等于1的判断，2>=1，在判断是否会等于1或2，2等于1或2，进行返回
  37.  
  38. 第三次第一个test，返回，1
  39. 第三次第二个test，返回1
  40. 第二次第一个test，返回2
  41. 第二次第二个test，返回1
  42. 第一次返回调用处，返回3
  43.  
  44. 3

 


五、猴子吃桃问题
有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个。以后的每天猴子都吃其中的一半，然后再多吃一个。
当第10天时，想再吃时（还没有吃），发现只有一个桃子了。问最初有多少个桃子。
 

  1. public class MonkeyPeach {
  2.     public static void main(String[] args) {
  3.         int day = 1;
  4.         int a = MonkeyPeach.test(day);
  5.         if (a != -1) {
  6.             System.out.println("第" + day + "天有" + a + "个桃");
  7.         }
  8.     }
  9.  
  10.     public static int test(int day) {
  11.         if (day == 10) { // 第十天只有1个桃
  12.             return 1;
  13.         } else if (day >= 1 && day <= 9) { //天数必须在1-10天之内
  14.             return (test(day + 1) + 1) * 2;
  15.         } else {
  16.             System.out.println("day必须在1-10之间");
  17.             return -1;
  18.         }
  19.     }
  20. }
  21.  
  22.  
  23. 思路分析：逆推
  24. 1. day10 有 1个桃子
  25. 2. day9  有 (day10+1)*2=4 个桃子  4/2-1=1
  26. 3. day8  有 (day9+1)*2=10 个桃子  10/2-1=4
  27. 规律就是 前一天的桃子 = (后一天的桃子 +1)*2
  28.  
  29. 输入天数可以获取当天桃子的个数,输入6
  30. 第一次调用test(6)，创建栈，出传入6，判断是否等于10，6不等于10，在判断是否大于等于1且小于等于9，6大于等于1且小于等于9，进行第二次调用test
  31. 第二次调用test(6+1)，创建栈，传入7，判断是否等于10，7不等于10，在判断是否大于等于1且小于等于9，7大于等于1且小于等于9，进行第三次调用test
  32. 第三次调用test(7+1)，创建栈，传入8，判断是否等于10，8不等于10，在判断是否大于等于1且小于等于9，8大于等于1且小于等于9，进行第四次调用test
  33. 第四次调用test(8+1)，创建栈，传入9，判断是否等于10，9不等于10，在判断是否大于等于1且小于等于9，9大于等于1且小于等于9，进行第五次调用test
  34. 第五次调用test(9+1)，创建栈，传入10，判断是否等于10，10等于10，进行返回，返回1
  35. 第五次调用，return 1，返回1，销毁栈
  36. 第四次调用，return (1 + 1) * 2，返回4，销毁栈
  37. 第五次调用，return (4 + 1) * 2，返回10，销毁栈
  38. 第五次调用，return (10 + 1) * 2，返回22，销毁栈
  39. 第五次调用，return (22 + 1) * 2，返回46，销毁栈
  40. 程序结束
  41.  
  42. 46

六、汉诺塔问题
把圆盘从a塔移动到c塔，且小于圆盘要在上面。

  1. public class HanoiTower {
  2.     public static void main(String[] args) {
  3.         Test test = new Test();
  4.         test.move(5,'A', 'B', 'C');
  5.     }
  6. }
  7.  
  8. class Test{
  9.     // num 表示要移动的个数，a,b,c 分别表示A塔 B塔 C塔
  10.     public static void move(int num, char a, char b, char c){
  11.         // 如果只有一个圆盘
  12.         if (num == 1){
  13.             System.out.println(a + "->" + c);
  14.         }else{
  15.             // 如果有多个圆盘，可以看成两个，最下面的和上面的所有圆盘(num-1)
  16.             //（1）先移动上面所有的圆盘到b，借助c
  17.             move(num-1, a, c, b);
  18.             //（2）把最下面的这个圆盘，移动到c
  19.             System.out.println(a + "->" + c);
  20.             //（3）再把b塔的所有圆盘，移动到c，借助a
  21.             move(num-1, b, a, c);
  22.         }
  23.     }
  24. }
  25.  
  26. 汉诺塔解读：
  27. main创建第一层栈，第一次调用move，创建第二层栈，传入 3,A,B,C，判断3是否等于1，3不等于1，
  28. 则进行第二次调用move，创建第三层栈，传入 2,A,C,B，判断2是否等于1，2不等于1
  29. 则进行第三次调用move，创建第四层栈，传入 1,A,B,C，判断1是否等于1，1等于1，输出 A->C，销毁栈，返回第三层
  30. 第三层栈，输出 A->B，
  31. 第四次调用move，创建第四层栈，传入1,C,A,B,判断1是否等于1，1等于1，输出 C->B，销毁栈，返回第三层
  32. 销毁栈，返回到第二层
  33. 第二层栈，输出 A->C，
  34. 第二层栈，进行第五次调用move，创建第三层栈，传入2,B,A,C，判断2是否等于1，2不等于1
  35. 则进行第六次调用move，创建第四层栈，传入 1,B,C,A，判断1是否等于1，1等于1，输出 B->A，销毁栈，返回第三层
  36. 第三层栈，输出B->C
  37. 第三层，进行第七次调用move，创建第四层栈，传入1,C,B,A，判断1是否等于1，1等于1，输出 A->C，销毁栈，返回第三层
  38. 销毁栈，返回第二层
  39. 销毁栈，返回第一层调用处
  40. 结束程序
  41.  
  42. A->C
  43. A->B
  44. C->B
  45. A->C
  46. B->A
  47. B->A
  48. C->A

 ▲表示输出

 

七、老鼠出迷宫问题

  1. public class Maze {
  2.     public static void main(String[] args) {
  3.         //创建迷宫，用二维数组表示 int[][] map = new int[8][7]
  4.         //先规定 map数组的元素值：0表示可以走，1表示障碍物
  5.         int[][] map = new int[8][7];
  6.  
  7.         // 设置障碍物
  8.         //将最上面的一行和最下面的一行，全部设置为1
  9.         for (int i = 0; i < 7; i++) {
  10.             map[0][i] = 1;
  11.             map[7][i] = 1;
  12.         }
  13.         //将最左面的一列和最右面的一列，全部设置为1
  14.         for (int i = 0; i < 8; i++) {
  15.             map[i][0] = 1;
  16.             map[i][6] = 1;
  17.         }
  18.         map[3][1] = 1;
  19.         map[3][2] = 1;
  20.  
  21.  
  22.         // 输出地图
  23.         System.out.println("====== 迷宫地图 ======");
  24.         for (int i = 0; i < map.length; i++) {
  25.             for (int j = 0; j < map[i].length; j++) {
  26.                 System.out.print(map[i][j] + " ");
  27.             }
  28.             System.out.println();
  29.         }
  30.  
  31.  
  32.         // 使用findWay给老鼠找路
  33.         test t = new test();
  34.         t.findWay(map,1,1);
  35.         System.out.println("====== 找路情况如下 ======");
  36.         for (int i = 0; i < map.length; i++) {
  37.             for (int j = 0; j < map[i].length; j++) {
  38.                 System.out.print(map[i][j] + " ");
  39.             }
  40.             System.out.println();
  41.         }
  42.     }
  43. }
  44.  
  45. // 使用递归回溯解决老鼠出迷宫
  46. // 1. findWay方法就是专门来找迷宫路径的
  47. // 2. 如果找到返回true，没有找到返回false
  48. // 3. map 就是二维数组，即表示迷宫
  49. // 4. x,y就是老鼠的坐标，初始化为 (1, 1)
  50. // 5. 因为是递归找路，所以先规定 map数组的各个值的含义
  51. //    0表示可以走，1表示障碍物，2表示可以走，3表示走过，但走不通是死路
  52. // 6. 当map[6][5]=2 就说明找到通路，就可以结束，否则就继续找。
  53. // 7. 先确定老鼠找路策略 下-> 右-> 上-> 左
  54. class test {
  55.     public boolean findWay(int[][] map, int x, int y) {
  56.         if (map[6][5] == 2) { //说明已经找到
  57.             return true;
  58.         } else {
  59.             if (map[x][y] == 0) { //当前这个位置0，说明表示可以走
  60.                 // 我们可以假定走通
  61.                 map[x][y] = 2;
  62.                 // 使用找路策略，来确定该位置是否真的可以走通
  63.                 // 下-> 右-> 上-> 左
  64.                 if (findWay(map, x + 1, y)) { //下
  65.                     return true;
  66.                 } else if (findWay(map, x, y + 1)) { //右
  67.                     return true;
  68.                 } else if (findWay(map, x - 1, y)) { //上
  69.                     return true;
  70.                 } else if (findWay(map, x, y - 1)) { //左
  71.                     return true;
  72.                 } else {
  73.                     map[x][y] = 3;
  74.                     return false;
  75.                 }
  76.             } else { //map[x][y] = 1, 2, 3
  77.                 return false;
  78.             }
  79.         }
  80.     }
  81. }
  82.  
  83.  
  84. ====== 迷宫地图 ======
  85. 1 1 1 1 1 1 1 
  86. 1 0 0 0 0 0 1 
  87. 1 0 0 0 0 0 1 
  88. 1 1 1 0 0 0 1 
  89. 1 0 0 0 0 0 1 
  90. 1 0 0 0 0 0 1 
  91. 1 0 0 0 0 0 1 
  92. 1 1 1 1 1 1 1 
  93. ====== 找路情况如下 ======
  94. 1 1 1 1 1 1 1 
  95. 1 2 0 0 0 0 1 
  96. 1 2 2 2 0 0 1 
  97. 1 1 1 2 0 0 1 
  98. 1 0 0 2 0 0 1 
  99. 1 0 0 2 0 0 1 
  100. 1 0 0 2 2 2 1 
  101. 1 1 1 1 1 1 1
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/590473
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号