＜蓝桥杯系列＞关于递归的深究

本文主要是介绍＜蓝桥杯系列＞关于递归的深究，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

目录

文章目录

前言

一、关于递归的基础问题

二、切蛋糕式求递归

1.求阶乘

2.打印从i—j的所有整数

3.数组求和

4.字符串逆转

总结

三、寻找规律求递归

1.公式法求递归

2.求最大公约数

总结

前言

递归在蓝桥杯的比赛中非常重要。

一、关于递归的基础问题

1.求阶乘

2.打印从i-j的所有数字

3.数组求和

4.字符串逆转

5.斐波那契数列

6.求最大公约数

二、切蛋糕式求递归

1.求阶乘

代码如下：

public class Recursion {public static void main(String[] args) {// TODO 自动生成的方法存根System.out.print(f1(3));}//求阶乘private static int f1(int i){if(i==1){return 1;}else {return i*f1(i-1);  }}}

解决思路：

这种题目就是找到递归切下去的那个点和终结递归的条件。

2.打印从i—j的所有整数

代码如下（示例）：

public class Recursion {public static void main(String[] args) {// TODO 自动生成的方法存根f2(3,6);}//打印从i-j所有的整数private static void f2(int i,int j){if(i>j){return;}else {System.out.print(" "+i);f2(i+1,j);}}
}

解决思路：

和上面的阶乘问题一样，不过就是把返回值变成了打印然后寻找递归的要素。

3.数组求和

代码如下（示例）：

public class Recursion {public static void main(String[] args) {// TODO 自动生成的方法存根System.out.println(f3(new int[]{1,3,4,5},3));}//数组求和private static int f3(int arr[],int i) {if(i==0) {//终止条件return arr[i];}else{return arr[i]+f3(arr,i-1);}}
}

解决思路：

类比阶乘的算法，把整个数组切成最后一个元素和前面的所有元素，然后以此递推。

4.字符串逆转

代码如下（示例）：

public class Recursion {public static void main(String[] args) {// TODO 自动生成的方法存根System.out.println(f4("abcdefg",6));}//字符串逆转   private static String f4(String str,int end){if(end==0) {   return str.charAt(0)+"";}else {return str.charAt(end)+f4(str,end-1);}}
}

总结

上面几个经典的递归案列，都是对寻找到递归的终止条件以及递归重复的那一部分，然后进行循环去切蛋糕。

比如：求数组之和与数组的阶乘字符串的逆转，都是找到了终止（条件为0的时候），然后把前面几部分按规律切下去。

三、寻找规律求递归

1.公式法求递归

代码如下：

public class Recursion {public static void main(String[] args) {// TODO 自动生成的方法存根System.out.println(f5(7));}//斐波那契数列private static int f5(int i){//斐波那契数列 为  1 1 2 3 5 8 13//公式为  f(i-1)+f(i-2)if(i<3){return 1;}else {return f5(i-1)+f5(i-2);}}}

解决思路：

根据数列寻找公式然后进行公式法处理

2.求最大公约数

代码如下（示例）：

public class Recursion {public static void main(String[] args) {// TODO 自动生成的方法存根System.out.println(f6(3,7));}/*最大公约数首先用 m%n  如果整除了 那就返回n如果未整除 就用n%余数 直到余数为0返回*/private static int f6(int m,int n) { //理解的不够透彻if(n==0)return m;return f6(n,m%n);}}

解决思路：

辗转相除法：先利用他们之间的关系，然后找到递归的规律。