c++算法之递归

发布时间:2024年01月13日

目录

递归

解释递归的两个关键要素:

基本情况(递归终止条件)

递归表达式(递归调用)

递归如何实现

递归和循环的比较

例题

斐波那契数列

题目描述

题解

数的计算

题目描述

输入描述

输出描述

输入输出示例

分析


递归

概念:递归是指函数直接或间接调用自身的过程

解释递归的两个关键要素:

基本情况(递归终止条件)

递归函数的一个条件,当满足该条件时,递归终止,避免无限递归。可以理解为直接解决极小规模问题的方法。

递归表达式(递归调用)

递归函数中的语句,用于解决规模更小的子问题,再将子问题的答案合并成为当前问题的答案。

递归如何实现

递归函数的基本结构如下:

返回类型 函数名(参数列表){
    //基本情况(递归终止条件)
    if(满足终止条件){
    //    返回终止条件下的结果
    }
    //递归表达式(递归调用)
    else{
    //将问题分解为规模更小的子问题
    //使用递归调用解决子问题
    //返回子问题的结果
    }
}

实现过程:

1.将大问题分解为规模更小的子问题

2.使用递归调用解决每个子问题

3.通过递归终止条件来结束递归

设计时需要注意的细节:

1.确保递归一定能到递归出口,避免无限递归,这可能导致TLE(超时)、MLE(超内存)或RE(运行错误)。

2.考虑边界问题,有时候递归出口不止一个。

3.避免不必要的重复计算,尽可能优化递归函数的性能(例如使用记忆化)。

递归和循环的比较

递归的特点:

1.直观、简洁、易于理解和实现

2、适用于问题的规模可以通过递归调用不断减小的情况

3、可以处理复杂的数据结构和算法,如树和图的遍历

4、存在栈溢出风险(栈空间一般只有8MB,所以递归层数不宜过深,一般不超过1e6层)

循环的特点:

1、直接控制流程,效率较高

2、适用于问题的规模没有明显的缩减,或者需要特定的迭代次数

3、适合处理大部分的动态规划问题

在部分情况下,递归和循环可以相互转换

例题

斐波那契数列

题目描述

已知F(1)=F(2)=1;

n>3时F(n)=F(n-1)+F(n-2)

输入n,求F(n),n<100000,结果对le9+7取模

题解

#include<iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
const ll p = 1e9 + 7;
//带备忘录递归
ll dp[N];

ll fib(int n)
{
	if (dp[n])return dp[n];//计算过的斐波那契那一位就不会重复计算了
	if (n == 1 || n == 2)return 1;
	else return dp[n] = (fib(n - 1) + fib(n - 2))%p;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	cout << fib(n) << endl;
	system("pause");
	return 0;
}

数的计算

题目描述

我们要求找出具有以下质数的个数(包含输入的自然数n)

先输入一个自然数n(n<1000),然后对此自然数按照如下方法进行处理

1.不做任何操作

2、在它的左边加上一个自然数,但该自然数不能超过原数的一半

3、加上数后,继续按此规则进行处理,直到不能再加自然数为止

输入描述

输入一个正整数n

输出描述

输出一个整数,表示具有该质数的个数

输入输出示例

输入6? ? ? ? 输出6

#include<iostream>
using namespace std;
const int N = 20;
int a[N];

int dfs(int deep)//deep表示当前的深度
{
	int res = 1;
	for (int i = 1; i <= a[deep - 1] / 2; ++i)//不能超过原来数字的一半
	{
		a[deep] = i;
		res += dfs(deep + 1);//向下一层去搜索
	}
	return res;
}
int main()
{
	int n; cin >> n;
	a[1] = n;
	cout << dfs(2) << endl;
	system("pause");
	return 0;
}

分析

首先,初始状态a[1]=n,拿n=6来说,dfs(2)进入后?

在for循环中for(i=1;i<=6/2=3;i++)即三个状态

1、a[2]=1 ???????????????? ?res+=dfs(3)

2、a[2]=2 a[3]=1????????res+=dfs(3)+dfs(4)

3、a[2]=3 a[3]=1? ? ? ? res+=dfs(3)+dfs(4)

所以最后结果为6

文章来源:https://blog.csdn.net/weixin_63201442/article/details/135565662
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。