一、基本概念
递归算法是一种直接或者间接调用自身函数或者方法的算法。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); } }