前言:
眼前我们对“递归算法的好处”大致比较注意,同学们都想要剖析一些“递归算法的好处”的相关文章。那么小编在网摘上搜集了一些有关“递归算法的好处””的相关文章,希望姐妹们能喜欢,兄弟们一起来学习一下吧!递归算法和递推算法无论是在ACM竞赛还是项目工程上都有着极为广泛的应用,但想要完全掌握两者的思想并不容易,对于刚刚接触编程的人来说更是这样,我在初次接触递归递推时就吃了很多的苦头,除了当时对编程语言不太熟悉之外,最大的原因就是难以理解其中的思想,本文将二者结合代码分别讲解,力求以"理论+实践"的方式使读者明白两种算法。一箭双雕,一文双递。
一.递归和递推的区别
学习递归递推的一个容易遇到的问题就是混淆二者的概念。所以学习时首先就要明白二者的区别。
二者的区别也可以看做二者的概念。
递归:一个方法/函数的自我嵌套,从结果出发一直向前回溯到初始状态(值),是一种程序自身调用自身的技巧,类似于套娃。举个栗子。
从前有座山,山里有座庙,庙里有个老和尚,在给小和尚讲故事。讲的什么故事呢?从前有座山,山里有座庙,庙里有个老和尚,在给小和尚讲故事。讲什么故事呢?从前有座山,山里有座庙,庙里有个老和尚,在给小和尚讲故事。讲的什么故事呢?从前有座山,山里有座庙,庙里有个老和尚,在给小和尚讲故事
这个大家耳熟能详的"老和尚讲故事"就是典型的递归。
递推:与递归的从结果找初始状态(值)相反,递推是已知初始状态(值),一步步计算得到最后的结果。高中数学中的数列经常会使用递推式。如:
S(n) = S(n - 1) + n ; D(n)=D(n-1)+D(n-2)+3
从上述样例可以看出,一个数列的某一项是通过它的前一项或前几项通过某种计算得到的。
二.递归–自我调用,递尽而归1.递归条件
(1)原问题可以变成更简单,规模更小的子问题,且原问题和子问题相似。
(2)一定要存在递归出口,即递归的结束条件。比如设置某种情况,在这种情况下会使递归函数返回,做到递尽而归。否则函数会一直递归下去,造成死循环。
2.递归图解
"一图胜千言",用图解的方式可以更好的理解递归。
给出一个正整数n,计算出1+2+...+n的结果
这道题最快的方法是用求和公式,但是为了体现出递归的概念,这里采用递归的思想。
import java.util.Scanner;public class ADD { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); System.out.printf("sum=%d\n",sum(n)); } private static int sum(int n){ if(n==1)return 1;//到1开始返回 return sum(n-1)+n;//否则继续递归,当前值和递归返回值相加 }}
从图中可以看出,函数先是不断的调用自身,函数每调用一次,参数就减一,当参数减到一的时候,函数开始返回1给上一层,就这样一层层返回。
3.典型题的代码实现
既然是"理论+实践",那习题是必不可少的了。学习算法需要刷题,学好算法需要大量的习题作为支持。
递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
思路:首先根据题干要求,'*'是无法使用的,且一定要用递归来完成,所以我们很容易想到用"加法+递归"的方式实现。
代码:
class Solution { public int multiply(int A, int B) { return add(A,B); } public int add(int A,int B){ if(A==0)return 0; if(A>B)return add(B,A);//选择较小的数来作为控制调用次数的参数,可以节省时间和避免栈溢出 return add(A-1,B)+B; }}
注:此题来自leetcode。链接:
汉诺塔。 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝纳勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
这个传说是否真实我们不得而知,但是汉诺塔问题已经成为了学习递归时的一个再经典不过的问题了,在学习递归的过程中,十之八九都会遇到汉诺塔问题。
在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。
思路:我们把三根柱子分别命名为A,B,C,开始时所有盘子都叠在A柱子上,要通过若干步全部转移到C上。假设N=1,则可以直接把盘子从A放到C上。当N=2时,就无法直接从A搬到C上了,这时B的作用就体现出来了。当N>1时,B就起到了一个"中转站"的作用,盘子可以先放到B上寄存,等可以放到C上时再放。可以把N个盘子分成上面的N-1个和最底下的1个,先把上面的N-1个通过C放到B上,再把底下的1个放到C上,最后再把B上的N-1个通过A放到C上。说着容易,N-1个盘子怎么移动呢,这就是递归的用武之地了,我们已经把N的问题变成N-1的问题了,所以可以进一步变成N-2的问题,这样下去一直到1个盘子的问题
class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { int n=A.size();//得出盘子的数量 move(n,A,B,C);//通过B把盘子从A移动到C } public void move(int n,List<Integer> A, List<Integer> B, List<Integer> C){ if(n==1){//只有一个盘子时 C.add(A.get(A.size()-1)); A.remove(A.size()-1);//直接从A移到C return ; } move(n-1,A,C,B);//把n-1个盘子从A通过C转移到B C.add(A.get(A.size()-1));//最后一个直接放到C上 A.remove(A.size()-1); move(n-1,B,A,C);//再把n-1个盘子从B通过A转移到C }}
注:此题来自leetcode。链接:
三.递推–初值传递,层层推进1.一般方法
递推常常是某种规律用公式的形式表达出来,因此该算法一般都会先找出递推式,然后由递推式算出结果。
2.斐波那契数列
斐波那契数列是数学家莱昂纳多·斐波那契在研究兔子繁殖时引入的,也称为"兔子序列"。如下:
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , · · ·
这个序列解释起来很简单,序列前两项为1,从第三项开始每一项都是前两项之和。递推式可以看成
Fib[n]=1,n=0||n=1
Fib[n]=Fib[n-1]+Fib[n-2],n>=3
现在我们知道了数列的初值(前两项),也知道了递推式,求关于斐波那契数列的问题就很容易了。
public class Fibonacci { public static void main(String[] args) { int[] Fib=new int[10]; Fib[0]=1; Fib[1]=1;; for(int i=2;i<9;i++){ Fib[i]=Fib[i-1]+Fib[i-2]; } }}3.典型题的代码实现杨辉三角。杨辉三角是是二项式系数在三角形中的一种几何排列,最初是被用来探究(a+b)[^n]的展开问题,在计算机中也是组合数学和递推算法的常用模型。
·
通过上图可以看出,杨辉三角中每行的最左边和最右边的数都是1,且第n行就会有n个数字,一个数字是上面的两个数字之和。可求出的递推表达式为
tri[i][j] = tri[i-1][j-1] + tri[i-1][j]
public class Triangle { public static void main(String[] args) { int[][] tri=new int[33][33];//杨辉三角用数组存储 for(int i=0;i<=10;i++){ tri[i][0]=tri[i][i]=1;//每行的最左边和最右边的数都是1,所以先把两边的数都设置成1 for(int j=1;j<i;j++){//处理中间的内容 tri[i][j]=tri[i-1][j]+tri[i-1][j-1];//递推式,把上面两数相加得到下面的数 } }//打印三角 for(int i=0;i<=10;i++){ for(int j=0;j<=10;j++){ System.out.print(tri[i][j]+" "); } System.out.println(); } }}
输出结果数组中的值为0的项删除后,得到的结果如下
11 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1伯努利-欧拉错排问题。 问题的最初形式是错装信封的问题。假设有n个信封,n封信,每封信都有对应的信封。求每封信都被装错的可能有多少种。后来就慢慢演化为有n个元素,在某种方式的排列以后,每个元素都不在原来位置上的可能有多少种。
分析:设错装信封的可能数为D(n),首先拿出第n封信,按照规则可以放在除第n个信封之外的另外n-1个信封中,假设第n封信被放到了第k个信封中(k!=n),这时信和信封各减一,此时有两种可能。
第k封信被放在了第n个信封中,这时信和信封又各减一,就有n-2个信封,n-2封信,可能数为D(n-2)第k封信没有被放在第n个信封中,就有n-1个信封,n-1封信,第k封信既然一定不会被放到第n个信封中,那么第k封信就可以认为是第n封信,这样就相当于只是把第k封信和第k个信封拿走,而其它的不变,可能数为D(n-1)
两种可能相加就是一共的可能数,经分析得到递推式
D(n) = (D(n-2) + D(n-1)) * (n-1)
因为信k和信封k是从n-1个信和n-1个信封中任意抽取的,所以要在最外面乘以n-1
代码:
import java.util.Scanner;public class cuopai { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int[] D=new int[n+1]; if(n==1){ System.out.println(0); }else if(n==2){ System.out.println(1); }else if(n>=3){ D[1]=0; D[2]=1; for(int i=3;i<=n;i++){ D[i]=(i-1)*(D[i-1]+D[i-2]); } } System.out.println(D[n]); }}
如果您觉得这篇文章对您有所帮助,欢迎关注我的微信公众号–【悬浮流星】,阅读更多的类似文章。如果您发现该文章有错误或不足之处,也欢迎批评指正。
标签: #递归算法的好处