错排问题（一文学会递归递推）

递归算法和递推算法无论是在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=%dn",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。链接：https://leetcode-cn.com/problems/recursive-mulitply-lcci/

汉诺塔。 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝纳勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的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。链接：https://leetcode-cn.com/problems/hanota-lcci

三.递推–初值传递，层层推进

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的项删除后，得到的结果如下

1 1 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]); } }

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