递归算法搞不懂可以来看看这几个小例题（Java）

60 阅读 0 评论 40 点赞

我是靠谱客的博主温婉自行车，最近开发中收集的这篇文章主要介绍递归算法搞不懂可以来看看这几个小例题（Java），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、求n阶乘

public class 求n阶乘 {
	//main函数  实现参数定义和输出
	public static void main(String[] args) {
		int n=6;
		System.out.println(factorial(n));
		

	}
	//递归函数
	public static int factorial(int n){
		if(n==1){//函数出口，终止条件
			return 1;
		}
		return n*factorial(n-1);//调用自身
	}

输出结果：720

2、打印i~j

public class Main {
	//main函数  
	public static void main(String[] args) {
		f(1,10);//设置参数

	}
	public static void f(int i,int j){
		if(i>j){//终止条件
			return;
		}
		System.out.println(i);
		f(i+1,j);//调用自身
	}

}

输出结果：1 2 3 4 5 6 7 8 9 10

3、数组求和

public class Main{
    public static void main(String[] args) {
		int[] a={1,2,3,4,5,6,7,8,9,10};
		System.out.println(sum(a,0));
	}
    //数组求和
	public static int sum(int []arr,int begin){
		if(begin==arr.length-1){
			return arr[begin];
		}
		return arr[begin]+sum(arr,begin+1);
	}

}

输出结果：55

4、字符串反转

public class Main{
    public static void main(String[] args) {
        System.out.println(reverse("abcdef",5));
	}
    
    public static String reverse(String src,int end){
		if(end==0){
			return ""+src.charAt(0);
		}
		return ""+src.charAt(end)+reverse(src, end-1);
		
	}

}

输出结果：fedcba

5、斐波那契数

public class Main{
    public static int fib(int n){
		    if(n==1||n==2){
			    return 1;
		    }
			
		    return fib(n-1)+fib(n-2);
	    }
	
	 public static void main(String[] args) {
		
		   System.out.println(fib(8));
	 }
}

输出结果：21

6、最大公约数（欧几里得算法）

public class Main{
   public static int gcd(int m,int n){//m>n
		if(n==0){
			return m;
		}
		return gcd(n,m%n);
		//n>(m%n),不断用大数去mod小数
		//如m=36,n=24;gcd(24,36%24)得到gcd（12,24%12），继续gcd（0,12%0），此时n=0，输出最大公约数m=12
		//其实就是每一次进行模运算后，取模的结果给到n，而m则得到上一轮中n的值
	}
	
	 public static void main(String[] args) {
		
		  System.out.println(gcd(36,24));
	 }
}

输出结果：12

7、汉诺塔

本题目标是：将A（按从底向上为从大到小的顺序摆放）里的盘子放入C盘中（也是以这种顺序摆放），B盘做辅助，初始时B、C盘均为空。每次只能移动一个盘

import java.util.Scanner;

public class 汉诺塔 {
	static int time;
	public static void main(String[] args) {
		char A='A', B='B',C='C';
		System.out.println("请输入盘子 个数：");
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		hannoi(n, A, B, C);//调用递归函数
		sc.close();
	}
	
	public static void move(int number,char M,char N){
		System.out.println("第"+(++time)+"次移动， 盘子"+number+" "+M+"-->"+N);
	}
	public static void hannoi(int n,char A,char B,char C){
		if(n==1){
			move(n,A,C);
		}else{
			hannoi(n-1, A, C, B);//调用自身
			move(n,A,C);
			hannoi(n-1, B, A, C);
		}
	}

}

输出结果：