递归算法常见问题（Java）
问题：斐波那契数列,第1项和第2项都为1，后面每一项都为相邻的前俩项的和,求第n个数
解法：每一个数都为前俩个数之和，第1项和第2项都为1，所以写 方法f1(n)即为求第n个数，那么f1(n-1)为求第n-1个数，f(n-2)为第n-2个数。所以f1(n)=f1(n-1)+f1(n-2)，然后设置出口，n=1或者n=2时返回1。
public class Test2 {
public static void main(String[] args) {
System.out.println(f1(6));
}
//斐波那契数列,第1项和第2项都为1，后面每一项都为相邻的前俩项的和,求第n个数
//f1为求第n个数，第n个数为第n-1个数加上第n-2个数
static int f1(int n){
if(n==1||n==2)
return 1;
return f1(n-1)+f1(n-2);
}
}
问题：求m和n的最大公约数，m>n
解法：若m%n=0，则n即最大公约数，若为k，则m与n的最大公约数可转换为 n与k的最大公约数
public class Test2 {
public static void main(String[] args) {
System.out.println(f2(36, 24));
}
//斐波那契数列,第1项和第2项都为1，后面每一项都为相邻的前俩项的和,求第n个数
//f1为求第n个数，第n个数为第n-1个数加上第n-2个数
static int f2(int m,int n){
if(m%n==0)
return n;
return f2(n,m%n);
}
}问题：对无序数组arr进行排序，arr数组大小为k
解法：对无序数组arr排序 等价于 对前k-1个元素排序后，在对第k个元素插入排序。先进行第1个元素和第2个元素的排序，然后对第3个元素插入排序，然后对第4个元素插入排序....不断递归。
public class Test2 {
public static void main(String[] args) {
int[] arr= new int[]{9,9,7,6,5,4,3,2,1};
f3(arr,arr.length-1);
for (int i : arr) {
System.out.println(i);
}
}
static void f3(int[] arr,int k){
if(k==0)
return;
//对前k-1个元素进行排序
f3(arr,k-1);
//把位置k的元素插到前面
int x=arr[k];
int index=k-1;
while(index>=0 && x<arr[index]){
arr[index+1]=arr[index];
index--;
}
arr[index+1]=x;
}
}问题：汉诺塔
将1～N从a移动到c，b作为辅助
等价于：将1～N-1从a移动到b，将N移动到c，这时a为空，c为空（此时c有N但因为N不用动了，所以看作为空），然后在把1～N-1移动到c，a为辅助。
public class Test2 {
public static void main(String[] args) {
f4(3,"A","C","B");
}
//N个小盘子，from初始柱子，to目标柱子，help辅助柱子
static void f4(int n,String from,String to,String help){
if(n==1){
System.out.println("move"+n+"from"+from+"to"+to);
}else {
f4(n-1,from,help,to); //把前n-1个盘子移到辅助柱子上
System.out.println("move"+n+"from"+from+"to"+to);//n号盘子可以到达目标柱子
f4(n-1,help,to,from); //n-1个盘子回到目标柱子
}
}
}问题：上楼梯、一共n阶，一次性可以上1阶、2阶或3阶，问多少种走楼梯的方法
上第n阶时，有三种情况，它可以从第n-1阶上1阶、从第n-2阶上2阶、从第n-3阶上3阶。
所有f(n)=f(n-1)+f(n-2)+f(n-3)。
public class Test2 {
public static void main(String[] args) {
System.out.println(f1(8));
}
static int f1(int n){
if(n==1)return 1;
if(n==2)return 2;
if(n==3)return 4;
return f1(n-3)+f1(n-2)+f1(n-1);
}
}问题：旋转数组，把一个递增数组的前若干个序列搬到该数组的最后，比如{1,2,3,4,5}->{3,4,5,1,2}，求该数组的最小值
解法：最小值一定在无序的那一半中。
public class Test2 {
public static void main(String[] args) {
}
//最小值一定在无序的那一半中。
static int f2(int[] arr){
int begin=0,end=arr.length-1;
//考虑没有旋转这种特殊旋转
if(arr[begin]<arr[end])return arr[begin];
while(begin+1<end){
int mid=begin+((end-begin)>>1);
if(arr[mid]>arr[begin]){ //左侧为有序
begin=mid;
}else{ //右侧有序
end=mid;
}
}
return arr[end];
}
}问题：在给定一个无序的数组中，找出最长连续递增的子序列
解法：找到第一个递增子序列的长度，然后递归下一个递增子序列的长度，直到遍历完数组
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{1,9,4,5,6,7,8,9,3,6,7};
int[]ans=f4(arr,0);
for(int i=0;i<ans.length;i++){
System.out.println(ans[i]);
}
}
static int[] f4(int[] arr,int start){
if(start>=arr.length)return new int[]{};
int count=1,index=start;
while(index<arr.length-1 &&arr[index+1]>arr[index]){
index++;
count++;
}
int[] ans= new int[count];
for(int i=start;i<start+count;i++){
ans[i-start]=arr[i];
}
int[] a=f4(arr,start+count);
return count>a.length?ans:a;
}
}问题：设计一个高效的求a的n次幂的算法
public class Test2 {
public static void main(String[] args) {
int n = -3
int ans=f5(2,Math.abs(n));
System.out.println(n>=0?ans:("1/"+ans));
}
static int f5(int a,int n){
if(n==0)return 1;
int ans=a;
int ex=1;//指数
while((ex<<1)<=n){
ans*=ans;
ex<<=1;
}
//差n-ex次方
ans*=f5(a,n-ex);
return ans;
}
}原文地址：https://blog.csdn.net/hguhbh/article/details/144744994
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！