龙空技术网

一文学会递归递推

堆栈树图 217

前言:

眼前我们对“递归算法的好处”大致比较注意,同学们都想要剖析一些“递归算法的好处”的相关文章。那么小编在网摘上搜集了一些有关“递归算法的好处””的相关文章,希望姐妹们能喜欢,兄弟们一起来学习一下吧!

递归算法和递推算法无论是在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]);    }}

如果您觉得这篇文章对您有所帮助,欢迎关注我的微信公众号–【悬浮流星】,阅读更多的类似文章。如果您发现该文章有错误或不足之处,也欢迎批评指正。

标签: #递归算法的好处