递归算法

2024-07-12 01:36| 来源: 网络整理| 查看: 265

To iterate is human,to recurse divine. ---L.Peter Deutsch

这句经典名言体现了递归算法的重要性，虽然执行效率不如迭代法，但它可以使那些很复杂的问题化成简单化。

递归一、递归概念二、程序示例1、划一刀思维（切蛋糕思维）（1）n的阶乘问题描述：求5的阶乘图解理解代码（2）打印i——j的值代码（3）对array的所有元素求和代码（4）字符串翻转代码小结2、多规模的子问题（1）斐波拉契问题描述代码（2）最大公约数问题描述代码小结三、总结

一、递归概念

递归，在数学与计算机科学中，是指在方法的定义中使用方法自身。也就是说，递归算法是一种直接或者间接调用自身方法的算法。简言之：在定义自身的同时又出现自身的直接或间接调用。

注意：递归必须要有一个退出的条件! 在这里插入图片描述

递归算法解决问题的特点： 1）递归就是方法里调用自身。 2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。

其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。

二、程序示例 1、划一刀思维（切蛋糕思维）（1）n的阶乘问题描述：求5的阶乘图解理解

在这里插入图片描述

代码 public class Demo6 { public static void main(String[] args) { System.out.println(fact(5)); } /** * 求n的阶乘f1（n) 求n的阶乘--->fact（n-1）求n-1的阶乘 * 1.找重复(规模更小）；n*(n-1)的阶乘，求n-1的阶乘是原问题的重复（规模更小）——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static int fact(int n) { if(n == 1) { return n = 1; }else { return n*fact(n-1); } } }

运行结果：在这里插入图片描述

（2）打印i——j的值代码 public class Demo6 { public static void main(String[] args) { fact(1,10); } /** * 打印i——j的值 * 1.找重复(规模更小）；i越来越靠近j——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static void fact(int i, int j) { if(i > j) { return ; }else { System.out.println(i); fact(i+1, j) } } }

运行结果：在这里插入图片描述

（3）对array的所有元素求和代码 public class Demo6 { public static void main(String[] args) { System.out.println(fact(new int[] {1,5,8,10,55}, 0)); } /** * 对array的所有元素求和 * 1.找重复(规模更小）；开始begin一直变化——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static int fact(int array[], int begin) { if(begin == array.length-1) { return array[begin]; }else { return array[begin] + fact(array,begin + 1); } } }

运行结果：在这里插入图片描述

（4）字符串翻转代码 public class Demo6 { public static void main(String[] args) { System.out.println(reverse("abcdef", 5)); } /** * 字符串翻转 * 1.找重复(规模更小）；开始end一直变化——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static String reverse(String src, int end) { if(end == 0) { return "" + src.charAt(end);//charAt是按照索引获得字符串的指定字符 }else { return src.charAt(end) + reverse(src, end - 1); } } }

运行结果：在这里插入图片描述

小结

分解为：直接量 + 小规模子问题

2、多规模的子问题（1）斐波拉契问题描述

1,1,2,3,5,8… 递推公式f(n) = f(n-1) + f(n-2)

代码 public class Demo6 { public static void main(String[] args) { System.out.println(fib(10)); } /** * 斐波拉契：1,1,2,3,5,8... 递推公式f(n) = f(n-1) + f(n-2) * 1.找重复(规模更小）；n一直变化——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static int fib(int n) { if(n == 1 || n == 2) { return 1; }else { return fib(n-1) + fib(n-2); } } }

运行结果：在这里插入图片描述

（2）最大公约数问题描述

最大公约数 f(m,n) = f(n,m%n)

代码 public class Demo6 { public static void main(String[] args) { System.out.println(f4(10,3)); } /** * 最大公约数 f(m,n) = f(n,m%n) * 1.找重复(规模更小）；n一直变化——子问题 * 2.找变化；变化的量应作为参数 * 3.找边界；出口 */ public static int f4(int m, int n) { if(n == 0) { return m; }else { return f4(n,m%n); } } }

运行结果：在这里插入图片描述

小结

分解多规模的子问题：划不开，有没有递推公式？有没有等价转换？

三、总结找重复： 1.找到一种划分的方法 2.找到递推公式或者等价转换这些都是父问题转化为求解子问题找变化的量：变化的通常要作为参数找出口

（ps：平时做题什么之类的，能用循环都不要用递归算法）

【本文地址】

递归算法

递归算法

今日新闻

推荐新闻