算法系列之递归算法5个简单实例
4⽉1号的蓝桥杯⽐赛快来了，报了名的⼩编⽇夜操劳的准备着~~~
只想默默地说⼀句，这个算法是真的难~
已经不想吐槽它折磨我的这20天了~
每当看到⾃⼰⽤很冗长的代码完成题⽬，⼤佬们简单的⼏⾏代码轻松解决，⼩编的⼼啊，拔凉拔凉的~⽣⽆可恋~~~
⼤神请绕道，我不想再看到你们~~~
希望本篇⽂章对您有所帮助，是我最开⼼的事情。(泪奔~好不容易写好了~电脑崩了~只能粗糙的写成这样了~）想哭~~~~~~~~~~~~~~~~对不起你们~~~~~ 下次⼀定打⼀个字存⼀次草稿~（写了两个⼩时直接没了~）
作者：浪潮之巅的⼩萝⼘头(纯⼿打，求⽀持）
闲话少叙，今天⼩编给⼤家介绍的是由简单到稍微难⼀些的java递归算法的5道⼩题。
⾸先先简介下递归算法：
递归算法（英语：recursion algorithm）在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。递归式⽅法可以被⽤于解决很多的计算机科学问题，因此它是计算机科学中⼗分重要的⼀个概念。绝⼤多数编程语⾔⽀持函数的⾃调⽤，在这些语⾔中函数可以通过调⽤⾃⾝来进⾏递归。计算理论可以证明递归的作⽤可以完全取代循环，因此在很多函数编程语⾔（如Scheme）中习惯⽤递归来实现循环。
简洁的讲就是：可以不断的调⽤⾃⾝这个函数，直到满⾜⼀定条件结束递归，（⼀般都是递归到最⼩的单位之后进⾏回溯的过程）下⾯⼩编通过这五个由浅⾄深的题⽬带领⼤家更好的理解神奇的递归算法。
第⼀题：斐波那契数列
/
* F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）*/
任意输⼊⼀个正整数的，输出斐波那契数列正整数对应的值。
思路：本题给出了两个常量F(0)=1，F(1)=1和⼀个算式F(n)=F(n-1)+F(n-2)，那么就可以设计⼀个函数，调⽤这个函数，当输⼊的值为0或1的时候，返回1，当输⼊n>2时，不断的调⽤该函数，知道n=1为⽌，之后进⾏返回，算出F(n)的值。例如:n=3 F(3)=F(2)+F(1)，此时需要先调⽤函数计算F(2)的值，F(2)=F(1)+F(0)=2，之后再返回到F(3）上，则可计算出F(3)=3；
具体代码实现如下:
/* F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）*/
public class 斐波那契数列 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int Int();
System.out.println(f(n));
}
public static int f(int n){
if(n==0||n==1){
return 1;
}
else{
return f(n-1)+f(n-2);
}
}
}
第⼆题：阶乘运算
解释：/*
* ⼀个正整数的阶乘（factorial）是所有⼩于及等于该数的正整数的积，
* 并且0的阶乘为1。⾃然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表⽰法。* 亦即n!=1×2×3×...×n。阶乘亦可以递归⽅式定义：0!=1，n!=(n-1)!×n。
*/
直接看代码吧，⼼累~
代码如下：
/*
* ⼀个正整数的阶乘（factorial）是所有⼩于及等于该数的正整数的积，
* 并且0的阶乘为1。⾃然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表⽰法。
* 亦即n!=1×2×3×...×n。阶乘亦可以递归⽅式定义：0!=1，n!=(n-1)!×n。
*/
public class 阶乘运算 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int Int();
System.out.println(f(n));
}
public static int f(int n){
if(n==0){
return 1;
}
else{
return n*f(n-1);
}
}
}
第三题：汉诺塔
概念:/*汉诺塔：汉诺塔（⼜称河内塔）问题是源于印度⼀个古⽼传说的益智玩具。
* ⼤梵天创造世界的时候做了三根⾦刚⽯柱⼦，在⼀根柱⼦上从下往上按照⼤⼩顺序摞着64⽚黄⾦圆盘。* ⼤梵天命令婆罗门把圆盘从下⾯开始按⼤⼩顺序重新摆放在另⼀根柱⼦上。并且规定，
* 在⼩圆盘上不能放⼤圆盘，在三根柱⼦之间⼀次只能移动⼀个圆盘。*/
直接看代码:（扎⼼~）
public class 汉诺塔 {
public static int i=1;//记录补数
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int Int();
sc.close();
char a='a',b='b',c='c';
f(n,a,b,c);
}
public static void f(int n,char a,char b,char c){
if(n==1){
move(1,a,c);
}
else{
f(n-1,a,c,b);
move(n,a,c);
f(n-1,b,a,c);
}
}
public static void move(int n,char a,char c){
System.out.println("第"+i+"步：将"+n+"号盘⼦从"+a+"移动到"+c);
i++;
}
}
第四题：全排列
概念:/*
* 从n个不同元素中任取m（m≤n）个元素，按照⼀定的顺序排列起来，
* 叫做从n个不同元素中取出m个元素的⼀个排列。当m=n时所有的排列情况叫全排列。*/
直接看代码:
/*注释代码针对的是排列中出现重复的情况*/
public class 全排列 {
public static void main(String[] args) {
int array[]={1,2,3};
fullArray(array,0,array.length-1);
}
private static void fullArray(int[] array, int cursor, int end) {
if (cursor == end) {
System.out.String(array));
} else {
for (int i = cursor; i <= end; i++) {
/*if(!panduan(array,cursor,end)){
continue;
}*/
swap(array, cursor, i);
fullArray(array, cursor + 1, end);
swap(array, cursor, i); // ⽤于对之前交换过的数据进⾏还原
}
}
}
private static void swap(int array[],int cursor,int i){
int temp = array[cursor];
array[cursor]=array[i];
array[i]=temp;
}
/*private static boolean panduan(int arr[],int start,int end){
for(int i=start;i<end;i++){
if(arr[i]==arr[end]){
return false;
}
}
return true;
}*/
编程递归函数}
最终的boss：整数划分
概念：/*
正整数n表⽰成⼀系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表⽰称为正整数n的划分。整数划分问题便是求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。*/

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。