前言
许多人对于递归觉得难以理解,其实最主要的原因还是自己少做少练了,今天小编就给大家带来一些经典的递归实例,希望有助于大家提高对代码的理解力。喜欢的朋友可以点赞留言哦,促进小编的进步!
一 阶乘问题
求n的阶乘
import java.util.Scanner; public class demoone { public static void main(String[] args) { // 递归求 N 的阶乘 Scanner sc = new Scanner(System.in);//从键盘读取一个数 int a = sc.nextInt();//将该数放入一个变量里面 int ret = jiecheng(a);//定义一个变量用于接收返回值 System.out.println(ret); } public static int jiecheng(int n){ if(n==1){ return 1;//这就是一个趋于终止的条件 }else{ return n*jiecheng(n-1);//这里就是使用递归,一直去调用自己 } } }
二 求和问题
递归求1+2+3+……+n的和
import java.util.Scanner; public class demoone { //实现代码: 递归求 1 + 2 + 3 + ... + n public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); System.out.println(sum(a)); } public static int sum(int n){ if(n==1){ return 1; }else{ return n+sum(n-1); } } }
三 打印数字问题
import java.util.Scanner; public class demoone { // 实现代码: 按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4) public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); printnum(a); } public static void printnum(int n){ if(n<10){ System.out.print(n+" ");//不换行输出,空格隔开,以示区别 }else{ printnum(n/10); System.out.print(n%10+" ");//不换行输出,空格隔开,以示区别 } } }
四 求每个位数相加问题
例:输入1234 结果:10(1+2+3+4)
import java.util.Scanner; public class demoone { //5. 实现代码: 写一个递归方法,输入一个非负整数,返回组成它的数字之和. public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a = sc.nextInt(); int ret = sumprint(a); System.out.println(ret); } public static int sumprint(int n){ if(n<10){ return n; }else{ return sumprint(n/10)+n%10; } } }
五 斐波那契数列
法一(不推荐):这里会有一个明显的缺点,就是当数字越来越大的时候,我们的运算速度就明显会变慢,这不会是我们想要的结果,所以这种方法我们了解就可以,不推荐使用这个方法。
import java.util.Scanner; public class demoone { //斐波那契数列 public static void main(String[] args) { Scanner sc =new Scanner(System.in); int a = sc.nextInt(); System.out.println(fib(a)); } public static int fib(int n){ if(n==1||n==2){ return 1; }else{ return fib(n-1)+fib(n-2);//斐波那契数列的特点,后一项等于前两项的和,这个就是从后往前推的一个思路 } } }
法二(迭代循环,极力推荐)
import java.util.Scanner; public class demoone { //斐波那契数列 public static void main(String[] args) { Scanner sc =new Scanner(System.in); int a = sc.nextInt(); System.out.println(fib(a)); } public static int fib(int n){ if(n==1||n==2){ return 1; } int b = 1; int c = 1; int d = 0; for(int i = 3;i<=n;i++){//迭代循环,这里利用循环迭代,从前面加到后面,减少了很多运算量,大大提高运算效率 d = b+c; b=c; c=d; } return d; } }
六 经典问题:青蛙跳台阶问题
public class demoone { /*青蛙跳台阶问题: 青蛙一次可以跳1个台阶,或者两个台阶,问此时跳n级台阶有几种跳法 其实,遇到这种问题,我们先具体化分析,找出其中的规律。然后在进行 编写程旭就会更简单了,首先青蛙跳1级台阶只有1种跳法,2级台阶有两种跳法 ,3级台阶有3张跳法,4级台阶有5种跳法,那么这个时候规律就可以看出来了,也就是说青蛙 跳3级台阶的跳法等于1级与2级的和,4级等于3级与2级的和。这样问题就被简化成一个斐波那契数列了 */ public static void main(String[] args) { Scanner sc =new Scanner(System.in); int b = sc.nextInt(); System.out.println(frogdump(b)); } public static int frogdump(int n){ if(n==1||n==2){ return n; } int a = 1; int b = 2; int c = 0; for(int i=3;i<=n;i++){ c=a+b; a=b; b=c; } return c; } }
七 经典问题:汉诺塔问题
public class qq { public static void main(String[] args) { hannio(3,'Q','W','R'); } public static void move(char a,char b){ System.out.print(a+"->"+b+" "); } /* 这里的one代表的是初始第一根柱子 two代表的是中转盘子的第二根柱子 three代表的是目的柱子 */ public static void hannio(int n,char one ,char two,char three){ if(n==1){ move(one,three);//终止条件,只有一个盘子的时候,直接从第一个柱子拿到第三根柱子 }else{ hannio(n-1,one,three,two);//把最大盘子上面的N-1个盘子通过第三根柱子移到第二根柱子上去 move(one,three);//此时就剩下最大的盘子在第一根柱子上面,直接移动到第三根柱子 hannio(n-1,two,one,three);//把第二根柱子上面的N-1根柱子通过第一根柱子移动到第三根柱子 } } }