递归,递推的是什么意思、读音？一文学会递归递推

大家好，关于递归,递推的是什么意思、读音很多朋友都还不太明白，今天小编就来为大家分享关于一文学会递归递推的知识，希望对各位有所帮助！

递归算法和递推算法无论是在ACM竞赛还是项目工程上都有着极为广泛的应用，但想要完全掌握两者的思想并不容易，对于刚刚接触编程的人来说更是这样，我在初次接触递归递推时就吃了很多的苦头，除了当时对编程语言不太熟悉之外，最大的原因就是难以理解其中的思想，本文将二者结合代码分别讲解，力求以"理论+实践"的方式使读者明白两种算法。一箭双雕，一文双递。

学习递归递推的一个容易遇到的问题就是混淆二者的概念。所以学习时首先就要明白二者的区别。

二者的区别也可以看做二者的概念。

从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲的什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲的什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事

这个大家耳熟能详的"老和尚讲故事"就是典型的递归。

S(n)=S(n-1)+n;D(n)=D(n-1)+D(n-2)+3

从上述样例可以看出，一个数列的某一项是通过它的前一项或前几项通过某种计算得到的。

(1)原问题可以变成更简单，规模更小的子问题，且原问题和子问题相似。

(2)一定要存在递归出口，即递归的结束条件。比如设置某种情况，在这种情况下会使递归函数返回，做到递尽而归。否则函数会一直递归下去，造成死循环。

"一图胜千言"，用图解的方式可以更好的理解递归。

给出一个正整数n，计算出1+2+...+n的结果

这道题最快的方法是用求和公式，但是为了体现出递归的概念，这里采用递归的思想。

importjava.util.Scanner;\n\npublicclassADD{\npublicstaticvoidmain(String[]args){\nScannerscanner=newScanner(System.in);\nintn=scanner.nextInt();\nSystem.out.printf("sum=%d\\n",sum(n));\n}\nprivatestaticintsum(intn){\nif(n==1)return1;//到1开始返回\nreturnsum(n-1)+n;//否则继续递归，当前值和递归返回值相加\n}\n}

递归图

从图中可以看出，函数先是不断的调用自身，函数每调用一次，参数就减一，当参数减到一的时候，函数开始返回1给上一层，就这样一层层返回。

既然是"理论+实践"，那习题是必不可少的了。学习算法需要刷题，学好算法需要大量的习题作为支持。

思路：首先根据题干要求，'*'是无法使用的，且一定要用递归来完成，所以我们很容易想到用"加法+递归"的方式实现。

classSolution{\npublicintmultiply(intA,intB){\nreturnadd(A,B);\n}\npublicintadd(intA,intB){\nif(A==0)return0;\nif(A>B)returnadd(B,A);//选择较小的数来作为控制调用次数的参数，可以节省时间和避免栈溢出\nreturnadd(A-1,B)+B;\n}\n}

注：此题来自leetcode。链接：https://leetcode-cn.com/problems/recursive-mulitply-lcci/

这个传说是否真实我们不得而知，但是汉诺塔问题已经成为了学习递归时的一个再经典不过的问题了，在学习递归的过程中，十之八九都会遇到汉诺塔问题。

在经典汉诺塔问题中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:

(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个盘子的问题

classSolution{\npublicvoidhanota(List<Integer>A,List<Integer>B,List<Integer>C){\nintn=A.size();//得出盘子的数量\nmove(n,A,B,C);//通过B把盘子从A移动到C\n}\npublicvoidmove(intn,List<Integer>A,List<Integer>B,List<Integer>C){\nif(n==1){//只有一个盘子时\nC.add(A.get(A.size()-1));\nA.remove(A.size()-1);//直接从A移到C\nreturn;\n}\nmove(n-1,A,C,B);//把n-1个盘子从A通过C转移到B\nC.add(A.get(A.size()-1));//最后一个直接放到C上\nA.remove(A.size()-1);\nmove(n-1,B,A,C);//再把n-1个盘子从B通过A转移到C\n}\n}

注：此题来自leetcode。链接：https://leetcode-cn.com/problems/hanota-lcci

递推常常是某种规律用公式的形式表达出来，因此该算法一般都会先找出递推式，然后由递推式算出结果。

斐波那契数列是数学家莱昂纳多·斐波那契在研究兔子繁殖时引入的，也称为"兔子序列"。如下：

这个序列解释起来很简单，序列前两项为1，从第三项开始每一项都是前两项之和。递推式可以看成

Fib[n]=1,n=0||n=1

Fib[n]=Fib[n-1]+Fib[n-2],n>=3

现在我们知道了数列的初值(前两项)，也知道了递推式，求关于斐波那契数列的问题就很容易了。

publicclassFibonacci{\npublicstaticvoidmain(String[]args){\nint[]Fib=newint[10];\nFib[0]=1;\nFib[1]=1;;\nfor(inti=2;i<9;i++){\nFib[i]=Fib[i-1]+Fib[i-2];\n}\n}\n}3.典型题的代码实现杨辉三角。杨辉三角是是二项式系数在三角形中的一种几何排列，最初是被用来探究(a+b)[^n]的展开问题，在计算机中也是组合数学和递推算法的常用模型。

·

通过上图可以看出，杨辉三角中每行的最左边和最右边的数都是1，且第n行就会有n个数字，一个数字是上面的两个数字之和。可求出的递推表达式为

tri[i][j]=tri[i-1][j-1]+tri[i-1][j]

publicclassTriangle{\npublicstaticvoidmain(String[]args){\nint[][]tri=newint[33][33];//杨辉三角用数组存储\nfor(inti=0;i<=10;i++){\ntri[i][0]=tri[i][i]=1;//每行的最左边和最右边的数都是1，所以先把两边的数都设置成1\nfor(intj=1;j<i;j++){//处理中间的内容\ntri[i][j]=tri[i-1][j]+tri[i-1][j-1];//递推式，把上面两数相加得到下面的数\n}\n}//打印三角\nfor(inti=0;i<=10;i++){\nfor(intj=0;j<=10;j++){\nSystem.out.print(tri[i][j]+"");\n}\nSystem.out.println();\n}\n}\n}

输出结果数组中的值为0的项删除后，得到的结果如下

1\n11\n121\n1331\n14641\n15101051\n1615201561\n172135352171\n18285670562881\n193684126126843691\n1104512021025221012045101伯努利-欧拉错排问题。问题的最初形式是错装信封的问题。假设有n个信封，n封信，每封信都有对应的信封。求每封信都被装错的可能有多少种。后来就慢慢演化为有n个元素，在某种方式的排列以后，每个元素都不在原来位置上的可能有多少种。

分析：设错装信封的可能数为D(n)，首先拿出第n封信，按照规则可以放在除第n个信封之外的另外n-1个信封中，假设第n封信被放到了第k个信封中(k!=n)，这时信和信封各减一，此时有两种可能。

两种可能相加就是一共的可能数，经分析得到递推式

D(n)=(D(n-2)+D(n-1))*(n-1)

因为信k和信封k是从n-1个信和n-1个信封中任意抽取的，所以要在最外面乘以n-1

importjava.util.Scanner;\n\npublicclasscuopai{\npublicstaticvoidmain(String[]args){\nScannerscanner=newScanner(System.in);\nintn=scanner.nextInt();\nint[]D=newint[n+1];\nif(n==1){\nSystem.out.println(0);\n}elseif(n==2){\nSystem.out.println(1);\n}elseif(n>=3){\nD[1]=0;\nD[2]=1;\nfor(inti=3;i<=n;i++){\nD[i]=(i-1)*(D[i-1]+D[i-2]);\n}\n}\nSystem.out.println(D[n]);\n}\n}

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

关于递归,递推的是什么意思、读音的内容到此结束，希望对大家有所帮助。