开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【递归】算法设计与分析 -> 正文阅读

[数据结构与算法]【递归】算法设计与分析

程序调用自身的编程技巧称为递归（ recursion）。

构成递归需具备的条件：

子问题须与原始问题为同样的事，且更为简单；

不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

(3)数据的结构形式是按递归定义的。

如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

🍁1406: 数字求和

题目描述

使用递归编写一个程序，计算一个正整数中所有数字之和。例如输入234，输出9。

输入

多组输入，每组输入一个正整数。

输出

输出结果，每个结果占一行。

样例输入

样例输出

Java题解

题目说要用递归，但是我们可以先用习惯的思路的做一做，那就是循环；

//n是输入的整数，ans是各位之和
int ans=0;
while(n!=0) {
    ans+=n%10;
    n/=10;
}

如何将其改为递归呢，可以做如下比较

循环的结束条件就是递归的退出条件
循环的的输入n和输出ans，就是递归的入参
循环每次n/=10进入下一个循环求其个位，递归也是将n/10作为入参自身调用求其个位

这么一看来，如何不会写递归不妨先想想怎么用循环写，再去尝试如何用递归解决

class Di{
	int Sum(int n,int ans) {
		if(n==0) {
			return ans;
		}else {
			return Sum(n/10,ans+n%10);
		}
	}
}

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        int n;
        Di di=new Di();
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()) {
            n=scanner.nextInt();
            int ans=0;
            ans=di.Sum(n, ans);
            System.out.println(ans);
             
        }
        scanner.close();
    }
 
}
 
class Di{
    int Sum(int n,int sum) {
        if(n==0) {
            return sum;
        }else {
            return Sum(n/10,sum+n%10);
        }
    }
}

🌺问题 B: 递归求和

题目描述

使用递归编写一个程序，求：
S(n)=1-1/2+1/3-1/4+1/5-1/6+......

输入

多组数据输入，每组输入一个正整数n。

输出

输出S(n)的计算结果（精确到小数点后六位）。

样例输入

样例输出

1.000000

Java题解

会了第一道其实这一到也就容易了不就是，偶数位减，奇数位加嘛


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		int n;
		D1 d1=new D1();
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()) {
			n=scanner.nextInt();
			double ans=d1.T(n, 0.0);
			System.out.printf("%.6f\n",ans);
		}
		scanner.close();

	}

}
class D1{
	public double T(int n,double ans) {
        //注意数据类型
		double i=n;
		if(n==1) {return ans+=1.0;}
        //如果是偶数位减去
		else if((n&1)==0){return T(n-1,ans-=(double)(1/i));}
        //如果是奇数位加上
		else {return T(n-1,ans+=(double)(1/i));}
	}
}

🌲问题 C: 倒序输出

题目描述

使用递归编写一个程序，逆序输出一个非负整数。例如输入1234，输出4321(不含前导0)。

输入

多组输入，每组输入一个非负整数。

输出

逆序输出结果，每个结果占一行。

样例输入

12
1230
0

样例输出

21
321
0

Java题解

这道题处理前导0可能会卡一会，不过其实只要在进入递归调用前先乘10，而不是在递归调用类乘10，与第一题有这一点点区别


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n;
		Dc dc=new Dc();
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()) {
			n=scanner.nextInt();
			int ans=dc.T(n,0);
			System.out.println(ans);
			
			
		}
		scanner.close();

	}

}
class Dc{
	public int T(int n,int ans) {
		if(n==0) {return ans+=0;}
		else {
			ans*=10;
            //在返回值前乘10可以巧妙去除前导零
			/*例如120，第一次调用T（12，ans+=(0))
			 * 第二次调用T（1，ans+=(2));
			 * 第二次调用T（0，ans+=(1));
			 */
			return T(n/10,ans+=((n%10)));
		}
	}
}

🌼1379: XP的楼梯

题目描述

XP是个淘气的孩子，他最近迷上了跳楼梯。他可以一次跳一级，也可以一次跳两级，他居然还能够一次跳三级楼梯（危险动作，请勿模仿）。某次，XP在跳完楼梯后突然想到一个问题，如果有n级楼梯，他从第一级开始往上跳，一直跳到第n级共有多少种不同的方案？你能帮他解决这个问题吗？当然，如果只有一级楼梯，很明显他只有一种选择。

输入

单组输入数据 n （0<n<30）

输出

输出一行结果

样例输入

样例输出

15902591

Java题解

这道题还是当初才进大学的时候做过，当时根本不知道怎么做，看到输出有这么大人都傻了

现在回头来做，呵呵🙂

斐波那契数列变形题

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int n;
		Lou lou=new Lou();
		Scanner scanner=new Scanner(System.in);
		n=scanner.nextInt();
		int ans=lou.T(n);
		System.out.println(ans);
		scanner.close();
	}

}

class Lou{
	public int T(int n) {
		if(n==1) {return 1;}
		if(n==2) {return 1;}
		if(n==3) {return 2;}
		
		else {return (T(n-3)+T(n-2)+T(n-1));}
	}
}

🌳问题 E: 蜂房

题目描述

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

输入

多组数据输入，每组数据包含两个正整数a, b，且 a<b。

输出

蜜蜂从蜂房a爬到蜂房b的可能路线数。

样例输入

1 2
3 4

样例输出

1
1

Java题解

这种题就是斐波那契数列的变形题

假设每一次蜜蜂都是从1开始爬

1-2有一种方法

1-3有两种方法

1-4其实就是可以看成从3号蜂房爬过来或者是从2号蜂房爬过来

就是f(4)=f(3)+f(2)

通式就是f(n)=f(n-1)+f(n-2)


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		int n,m;
		De de=new De();
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()) {
			n=scanner.nextInt();
			m=scanner.nextInt();
			
			//处理3-4蜂房
			int chazhi=n-1;
			m=m-chazhi;
			
			int ans=de.T(m);
			System.out.println(ans);
			
			
		}
		scanner.close();

	}

}
class De{
	public int T(int n) {
		if(n==1) {return 0;}
		if(n==2) {return 1;}
		if(n==3) {return 2;}
		else {
			return T(n-1)+T(n-2);
		}
	}
}

😫问题 G: 斐波那契数

题目描述

Kimi号称自己已经记住了前100000个斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。
当然，斐波那契数会很大。
因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位(无需输出前导0)。

输入

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出

对应每一组输入，输出第n个斐波那契数的最后6位。

样例输入

样例输出

Java题解

看着这个数据量就知道不能用递归来做了，肯定会超时的；但我还是用了递归，而且还用了大整数类写，结果写了一节课头都转晕了，还栈爆了，我也不知道对不对，反正先贴出来，说不定下次又遇到了

?Java大整数类：错误解法


import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		BigInteger n;
		Dg dg=new Dg();
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()) {
			n=scanner.nextBigInteger();
			System.out.println(n);
			BigInteger ans=dg.T(n);
			if(ans.toString().length()>=6) {
				System.out.println(ans);
			}else {
				int len=ans.toString().length();
				String aString=ans.toString().substring(len-7, len-1);
				System.out.println(aString);
			}
		}
		scanner.close();
	}

}

class Dg{
	public BigInteger T(BigInteger n) {
		
		BigInteger a=BigInteger.valueOf(1);
		BigInteger b=BigInteger.valueOf(2);
		if(n.equals(1)) {return a;}
		if(n.equals(2)) {return b;}
		else {
			return T(n.subtract(a)).add(T(n.subtract(b)));
			}
	}
}

我就用数组写吧，先是用java写的，直接存储数组里，呵呵，还是超时

?时间超限


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//Vector<Integer> ve=new Vector<Integer>();
		Scanner scanner=new Scanner(System.in);
		int n;
		while(scanner.hasNext()) {
			n=scanner.nextInt();
			
			int []num=new int[n+3];
            
			num[0]=1;num[1]=2;
            
			int ans=0;
			if(n==1) {
				ans=1;
			}else if(n==2){
				ans=2;
			}else {
				int i;
				for(i=2;i<n;i++){
					num[i]=(num[i-1]+num[i-2])%1000000;
				}
				ans=num[i-1];
			}
			
			System.out.println(ans);
			
			
		}
		scanner.close();
	}
}

换成c/c++来，想着c/c++不是快嘛，说不定用c/c++就过来，我看看到底有多快，考虑到cin和cout读取和输出数据慢，我还特意用了scanf()和printf()；呵呵，还是超时

?时间超限

#include<iostream>
#include<stdio.h>
using namespace std;
int num[100010];
int main(){

		int n;
		while((scanf("%d",&n))!=EOF) {	
			num[0]=1;num[1]=2;
			int ans=0;
            
			if(n==1) {
				ans=1;
			}else if(n==2){
				ans=2;
			}else {
				int i;
				for(i=2;i<n;i++){
					num[i]=(num[i-1]+num[i-2])%1000000;
				}
				ans=num[i-1];
			}

			printf("%d\n",ans);
		}
	}

实在想不出了，我就去问了我们班的OJ大佬，结果犯了一个以前就犯过的错误，而且还学到了时间超限到底是怎么回事

当然栈溢出并不是主要问题了，第三张图才是我的问题根源之处

改了之后立马就过了，其实自己之前做过大整数的题，当时自己就是这样处理的，一年不到就已经重蹈覆辙了，这学期一点要努力刷题👀

?c/c++:正确题解

#include<iostream>
#include<stdio.h>
using namespace std;
int MaxNum;
int Max=1000000;
int num[100010];
int main(){
		int n;
		num[0]=1;num[1]=2;
		for(int i=2;i<100001;i++){
            num[i]=(num[i-1]+num[i-2])%Max;
        }
		while((scanf("%d",&n))!=EOF) {

			int ans=0;
			ans=num[n-1];
			printf("%d\n",ans);
		}
	}

Java也交了一遍，也是一下子就过了

?Java题解



import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner scanner=new Scanner(System.in);
		int n;
		int []num=new int[100000+1];
		num[0]=1;num[1]=2;
		for(int i=2;i<100001;i++){
			num[i]=(num[i-1]+num[i-2])%1000000;
		}
		while(scanner.hasNext()) {
			n=scanner.nextInt();
			int ans=num[n-1];
			System.out.println(ans);
		}
		scanner.close();
	}
}