#创作计划#递归定义及应用
2025-02-12 18:26:33
发布于：北京
前言
递归 Recursion 是一种很常用的算法，这种算法比较易学，他与递推 Recurrence 一直都是相辅相成的。
本文将介绍递归含义，在题库挑选例题进行讲解，讨论与递推的相同与不同。
注意：本文有一些脚注，这些脚注是用来展示评测结果图片的。
正文
递归定义：
递归的定义如下：
- 将大问题持续分解成小问题
- 在小问题达到边界条件不能分割时开始进行回归过程
比如计算 ,把他用乘法表现出来是这样的：
如果把1~4加上括号，那就成了这样：
而被括号括起来的部分刚好是
而继续分割括号部分就会变成：
再分割就是：
最后再分割就是：
，所以往回带， ,所以。
在这个例子里， 是大问题，是小问题，是边界条件。
注意：如果没有边界条件，就会进入死循环。
比如这段代码：
#include<bits/stdc++.h>
using namespace std;
void cnt(int n){
cout << n;
return cnt(n+1);
}
int main(){
cnt(1);
}
这段代码没有边界条件，在运行时就会无限递归，在达到系统的边界条件之后停止。在我们的运行结果要进行评测时，就会OLE[1]。
例题：
- 入门难度：A29898.递归求n!
- 普及-难度：A7972.斐波那契数列
- 普及/提高-难度：A7975.斐波那契记忆化(此题是递归记忆化)
入门难度[A495.求阶乘和]：
此题我们先参考上面的例子和题目写一个递归函数:
long long fac(int num){
if(num <= 1) return 1;
return num*fac(num-1) % 998244353;
}
def fac(num):
if num <= 1:
return 1
return num*fac(num-1)
再在main函数进行调用，所以AC代码如下：
#include<bits/stdc++.h>
using namespace std;
long long fac(int num){
if(num <= 1) return 1;
return num*fac(num-1) % 998244353;
}
int main(){
int n;
cin >> n;
long long s = fac(n);
cout << s;
}
def fac(num):
if num <= 1:
return 1
return num*fac(num-1) % 998244353
n = int(input())
print(fac(n))
普及-难度[A7972.斐波那契数列]：
此题我们分析斐波那契数列的特点（第个数+第个数=第个数）需要进行“一边二”的递归，也就是。而根据题目所述，第个和第个数都为，所以边界条件即为在n == 1 or n == 2或者说n <= 2的时候返回1。
所以我们先写出一个递归函数：
long long f(int x){
if(x <= 2) return 1;
return f(x-1) + f(x-2);
}
def f(x):
if x <= 2:
return 1
return f(x-1) + f(x-2)
在main函数调用此函数即可，AC代码如下：
#include<iostream>
using namespace std;
long long f(int x){
if(x <= 2) return 1;
return f(x-1) + f(x-2);
}
int main(){
long long a;
cin >> a;
cout << f(a);
}
def f(x):
if x <= 2:
return 1
return f(x-1) + f(x-2)
n = int(input())
print(f(n))
普及/提高-难度[A7975.斐波那契记忆化]：
这题有一些难度，我们先如果写出上面的代码，那么就会TLE[2]：
我们来分析一下原因：
首先，我们先拿 举例，我们想一想就可以知道计算它需要用到的算式：
所以我们可以发现，，函数会计算和，，所以会计算两次。
我们就可以利用此特性进行记忆化，首先我们定义一个数组（列表）：
long long c[61]; //题目说了n<=60，我们可以只定义数组长度为61。C++默认int类型数组不初始化全部值都为0。
c = [0 for i in range(61)]
接下来定义一个函数，并添加边界条件：
long long f(int n){
if(n <= 2) return 1;
}
def f(n):
if n <= 2:
return 1
接下来，如果被计算过，那么我们就可以用索引取到相对应的数，如果没有计算过，其数为，我们就可以使用没计算为的特性检测此数是否被计算过。
if(c[n] != 0) return c[n];
if c[n] != 0:
return c[n]
最后计算没被计算过的值并返回相应值：
// C++
c[n] = f(n-1) + f(n-2);
return c[n];
# Python
c[n] = f(n-1) + f(n-2)
return c[n]
最后依然在main函数调用，AC代码如下：
#include<bits/stdc++.h>
using namespace std;
long long c[61];
long long f(int n){
if(n<=2) return 1;
if(c[n]!=0) return c[n];
c[n]=f(n-1)+f(n-2);
return c[n];
}
int main(){
int k;
cin >> k;
cout << f(k);
}
c = [0 for i in range(61)]
def f(n):
if n <= 2:
return 1
if c[n] != 0:
return c[n]
c[n] = f(n-1) + f(n-2)
return c[n]
k = int(input())
print(f(k))
递归与递推的相同与不同：
相同点：
- 重复结构：递归与递推都涉及到重复的计算过程。
- 分解问题：递归通过将问题分解成子问题来求解。
不同点：
- 计算过程：递归是将问题不断拆解成更小的子问题，在达到边界条件后往前带；递推是跟据已知的初始条件和公式，一步步地计算出后续的解。
- 思维方式：递归侧重于问题结构化；而递推侧重于构造明确的数学关系式。
示例——阶乘问题：
- 递归：通过调用自己来计算阶乘 ，直到达到基本情况。
- 递推：过显式公式逐步计算 , 从 开始，用 计算。
以下是两种方法的C++代码：
// 递归
#include<bits/stdc++.h>
using namespace std;
long long fac(int num){
if(num <= 1) return 1;
return num*fac(num-1);
}
int main(){
int n;
cin >> n;
long long s = fac(n);
cout << s;
}
// 递推
#include<bits/stdc++.h>
using namespace std;
long long fac(int n){
long long r = 1;
for (int i = 1; i <= n; i++){
r *= i;
}
return r;
}
int main(){
long long n;
cin >> n;
cout << fac(n) << endl;
return 0;
}
有帮助，赞一个