蓝桥杯递归算法
一、基本概念
递归算法是一种直接或者间接调用自身函数或者方法的算法。Java递归算法是基于Java语言实现的递归算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。
二、递归算法的优点
1）递归就是方法里调用自身。
2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。
三、常见问题的递归解决
3.1、求数组的和
package demo;
public class 递归求数组纸和arr {
public static void main(String[] args) {
int arr=f3(new int[]{
1,5,5,8,},0); //定义了一个新的数组new int[]
System.out.println(arr);
}
static int f3(int [] arr,int begin){
if (begin==arr.length-1){
//数组移动到最后一个元素时即数组的值为0时停止递归。
return arr[begin];
}
return arr[begin]+f3(arr,begin+1);
}
}
3.2、求一个数的阶乘
package demo;
public class 求一个数的阶乘 {
public static void main(String[] args) {
f1(1,10);
f(2);
}
static int f(int i){
if (i==1){
return 1;
}
return i*f(i-1);
}
//打印1-10的数字采用递归的方法。
//递归就是自己调用自己。其中static的函数为形参。方法中被调用的是实参。
static void f1(int i, int j){
if (i>j)//如果i大于就则就退出。防止出现死循环。
return ;
System.out.println(i);
f1(i+1,j);
}
}
3.3、斐波起啦数列和求最大公约数
package demo;
public class 斐波起啦数列 {
public static void main(String[] args) {
System.out.println(f1(20));
System.out.println(f2(9,2));
}
static int f1(int n){
//找出口
if (n==1||n==2)
return 1;
return f1(n-1)+f1(n-2);
}
//求最大公约数
static int f2(int m,int n){
if (m%n==0)
return m;
return f2(n,m%n);
}
}
3.4、字符串的翻转
package demo;
public class 字符串的翻转 {
public static void main(String[] args) {
System.out.println(f1("abcd",3));
}
static String f1(String src,int end){
if(end==0){
return ""+src.charAt(0);
}
int i=src.charAt(end);
System.out.println(i);
return src.charAt(end)+f1(src,end-1);
}
}
