算法系列之递归算法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；
具体代码实现如下:
package 递归算法;
import java.util.Scanner;
/* 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 n=sc.nextInt();
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。
*/
直接看代码吧，心累~
代码如下：
package 递归算法;
import java.util.Scanner;
/*
* 一个正整数的阶乘（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 n=sc.nextInt();
System.out.println(f(n));
}
public static int f(int n){
if(n==0){
return 1;
}
else{
return n*f(n-1);
}
}
}
第三题:汉诺塔
概念:/*汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。
* 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
* 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，
* 在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。*/
直接看代码:（扎心~）
package 递归算法;
import java.util.Scanner;
public class 汉诺塔 {
public static int i=1;//记录补数
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
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时所有的排列情况叫全排列。
*/
直接看代码:
package 递归算法;
import java.util.Arrays;
/*注释代码针对的是排列中出现重复的情况*/
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.println(Arrays.toString(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。*/
思路:
直接看代码吧，真心抱歉~
package 递归算法;
public class 整数划分 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
sc.close();
System.out.println(f(n,m));
}
public static int f(int n,int m){
if((n<1)||(m<1)){
return 0;
}
if((n==1)||(m==1))
return 1;
if(n<m){
return f(n,n);
}
if(n==m){
return f(n,n-1)+1;
}
return f(n,m-1)+f(n-m,m);
}
}