递归及其应用
递归：
定义：一个函数自己调用自己
满足条件：
- 递归必须得有一个明确的中止条件
- 该函数所处理的数据规模必须在递减
- 这个转化必须是可解的
循环和递归
递归：①易于理解 ②速度慢 ③存储空间大
循环：①不易理解 ②速度快 ③存储空间小
递归的引用：
- 树和森林就是以递归的方法定义的
- 树和图的很多算法都是以递归来实现
- 很多数学公式就是以递归的方式定义的
- 斐波那契数列：1 1 2 3 5 8 13……
找出数组中最大值：
Java
public static int getMax(int []array){
return process(array,0,array.length-1);
}
//array[L...R]范围求最大值
public static int process(int []array,int L,int R){
if(L==R){
return array[L];
}
int middle = L + (R - L) >> 1//求中电，位运算比除法来的更快
int leftMax = process(array,L,middle);
int rightMax = process(array,R,middle);
return Math.max(leftMax,rightMax);
}
等差求和：
C语言：
#include <stdio.h>
int f(int n);
int main()
{
int n;
scanf("%d",&n);
int sum = f(n);
printf("%d",sum);
return 0;
}
int f(int n){
if(n==1){
return n;
}else{
return f(n-1)+n;
}
}
Java：
import java.util.Scanner;
/**
* @创建人 HeXin
* @创建时间 2022/10/29
* @描述
*/
public class Main{
/**
*@BelongsProject: Recursion
*@BelongsPackage: Test01
*@Author: hexin
*@CreateTime: 2022-10-29 14:52
*@Description: TODO
*@Version: 1.0
*
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
getSum qiuhe = new getSum();
int sum = qiuhe.sum(n);
System.out.println(sum);
}
}
class getSum{
public int sum(int n){
if(n==1){
return 1;
}else{
return sum(n-1)+n;
}
}
}
阶乘：
C语言：
#include <stdio.h>
int f(int n);
int main()
{
int n;
scanf("%d",&n);
int ret = f(n);
printf("%d",ret);
return 0;
}
int f(int n){
if(n==1){
return n;
}else{
return f(n-1)*n;
}
}
Java:
import java.util.Scanner;
/**
* @创建人 HeXin
* @创建时间 2022/10/29
* @描述
*/
public class Main{
/**
*@BelongsProject: Recursion
*@BelongsPackage: Test01
*@Author: hexin
*@CreateTime: 2022-10-29 14:55
*@Description: TODO
*@Version: 1.0
*
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
getSum jiecheng = new getSum();
int sum = jiecheng.sum(n);
System.out.println(sum);
}
}
class getSum{
public int sum(int n){
if(n==1||n==0){
return 1;
}else{
return sum(n-1)*n;
}
}
}
斐波那契数列：
C语言(递归)：
#include <stdio.h>
int f(int n);
int main()
{
int n;
scanf("%d",&n);
int sum = f(n);
printf("%d",sum);
return 0;
}
int f(int n){
if(n<=2){
return 1;
}else{
return (f(n-1)+f(n-2));
}
}
//优点：思路清晰，代码简单。
//缺点：输入过大，会导致程序卡死，浪费内存。
C语言(非递归)：
#include <stdio.h>
int main()
{
int n;
int num[100]={0};
scanf("%d",&n);
num[1] = num[2] = 1;
if(n>2) {
for (int i = 3; i <=n; i++) {
num[i] = num[i - 1] + num[i - 2];
}
}else{
printf("1");
}
printf("%d",num[n]);
return 0;
}
Java:
class test {
public static void main(String[] args) {
/**
*
*@描述 斐波那契数列(非递归)
*@参数 [args]
*@返回值 void
*@创建人 HeXin
*@创建时间 2022/11/18
*@修改人和其它信息
*
*/
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int num[] = new int[100];
num[1] = num[2] = 1;
if (n > 2) {
for (int i = 3; i <= n; i++) {
num[i] = num[i - 1] + num[i - 2];
}
}else {
System.out.printf("1");
}
System.out.printf("%d", num[n]);
}
}
汉诺塔：
C语言：
#include <stdio.h>
void f(int n,char a,char b,char c);
int main()
{
char ch1 = 'A';
char ch2 = 'B';
char ch3 = 'C';
int n;
scanf("%d",&n);
f(n,ch1,ch2,ch3);
return 0;
}
void f(int n,char a,char b,char c){
if(n==1){
printf("编号为%d:%c->%c\n",n,a,c);//最后一个盘子直接从A柱子上移动到C
}else{
f(n-1,a,c,b);//将A柱子上的n-1个盘子借助C移动到B
printf("编号为%d:%c->%c\n",n,a,c);//直接将A柱子上的盘子从A移到C
f(n-1,b,a, c);//最后将B柱子上的n-1个盘子借助A移到C
}
}
Java:
import java.util.Scanner;
/**
* @创建人 HeXin
* @创建时间 2022/10/29
* @描述
*/
public class Main{
/**
*@BelongsProject: Recursion
*@BelongsPackage: Test01
*@Author: hexin
*@CreateTime: 2022-10-29 14:52
*@Description: TODO
*@Version: 1.0
*
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Hanota hanota = new Hanota();
hanota.hanota(n,'A','B','C');
}
}
class Hanota{
public void hanota(int n,char a,char b,char c){
if(n==1){
System.out.printf("%c->%c\n",a,c);
}else{
hanota(n-1,a,c,b);
System.out.printf("%c->%c\n",a,c);
hanota(n-1,b,a,c);
}
}
}
注：该文章为本人学习时的笔记，属于比较综合类型的，不是很美观。若有雷同，请谅解