递归算法题练习（数的计算、带备忘录的递归、计算函数值）

发布于

递归的介绍

概念:递归是指函数直接或间接调用自身的过程。 解释递归的两个关键要素: 基本情况(递归终止条件):递归函数中的一个条件，当满足该条件时，递归终止，避免无限递归。可以理解为直接解决极小规模问题的方法。递归表达式(递归调用):递归函数中的语句，用于解决规模更小的子问题再将子问题的答案合并成为当前问题的答案。

递归如何实现

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

实现过程:

  • 将大问题分解为规模更小的子问题。
  • 使用递归调用解决每个子问题。
  • 通过递归终止条件来结束递归。

设计时需注意的细节:

  1. 确保递归一定能到递归出口，避免无限递归，这可能导致TLE(超时)、MLE(超内存)、或RE(运行错误)
  2. 考虑边界条件，有时候递归出口不止一个。
  3. 避免不必要的重复计算，尽可能优化递归函数的性能(例如使用记忆化)。

递归和循环的比较

递归的特点:

  1. 直观、简洁，易于理解和实现
  2. 适用于问题的规模可以通过递归调用不断减小的情况。
  3. 可以处理复杂的数据结构和算法，如树和图的遍历。(线段树)
  4. 存在栈溢出风险(栈空间一般只有8MB，所以递归层数不宜过深一般不超过1e6层)。

循环的特点:

  • 1.直接控制流程，效率较高。(常数小)
  • 2.适用于问题的规模没有明显的缩减，或者需要特定的迭代次数。(二元组)
  • 3.适合处理大部分的动态规划问题

在部分情况下，递归和循环可以相互转化。(DFS)

例题:

（一、斐波那契数列，带备忘录的递归）

已知F(1)=F(2)= 1;n>3时F(n)=F(n-1)+F(n-2) 输入n，求F(n)，n<=100000，结果对1e9+7取模

如果直接使用递归，难以算出结果，需要优化

时间复杂度为

O(2^n)
代码语言：javascript
复制
#include <bits/stdc++.h>  
using namespace std;
using ll = long long; // 使用别名ll代表long long

const int N = 1e5 + 9;

const ll p = 1e9 + 7; // 定义模数p


ll fib(int n) {

if (n <= 2) return 1; // 基准情况

return (fib(n - 1) + fib(n - 2)) % p; // 计算并存储结果

}


int main() {

int n;

cin >> n;

for (int i = 1; i <= n; ++i) {

cout << fib(i) << '\n'; // 输出每个i的fibonacci数并换行

}

return 0;

}

优化方法：带备忘录的递归

时间复杂度为

O(n)
代码语言：javascript
复制
#include <bits/stdc++.h>

using namespace std;

using ll = long long; // 使用别名ll代表long long


const int N = 1e5 + 9;

const ll p = 1e9 + 7; // 定义模数p


ll dp[N]; // 定义dp数组作为备忘录


// 带备忘录的递归

ll fib(int n) {

if (dp[n]) return dp[n];

// 如果已经计算过，直接返回结果，不需要重复计算

if (n <= 2) return 1; // 基准情况

return dp[n] = (fib(n - 1) + fib(n - 2)) % p; // 计算并存储结果

}


int main() {

int n;

cin >> n;

for (int i = 1; i <= n; ++i) {

cout << fib(i) << '\n'; // 输出每个i的fibonacci数并换行

}

return 0;

}

（二、数的计算）

蓝桥 OJ 760

用户登录

题目描述
输入一个自然数 n(n < 1000)，我们对此自然数按照如下方法进行处理:
1.不作任何处理;
2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3.加上数后,继续按此规则进行处理,直到不能再加自然数为止。问总共可以产生多少个数。
输入描述
输入一个正整数 n。
输出描述
输出一个整数，表示答案。
输入输出样例

思路：

我们可以将题意转化一下，转化成在右边加上自然数，因为“在左边加上0”是没有意义的，不会改变这个数字大小，所以我们在右边也不能加上0。
用一个数组a记录下数字每一位上的数字是多少，然后枚举当前位上的数字，递归的向下去求方案数并求和即可。

代码语言：javascript
复制
#include<bits/stdc++.h>

using namespace std;


const int N = 20;

int a[N];


int dfs(int dep)// dep表示当前的深度

{

int res = 1;

// 枚举当前这层可以放下哪些数字

for (int i = 1; i <= a[dep - 1] / 2; ++i)

{

a[dep] = i;

res += dfs(dep + 1);

}

return res;

}


int main()

{

int n; cin >> n;

a[1] = n;

cout << dfs(2) << '\n';

return 0;

}

（三、计算函数值）

用户登录

问题描述：

在一个神秘的世界中，有一个传说中的神秘花园，被认为蕴藏着无限的知识。但要进入这个花园，访客必须解决一道神秘数学难题，这个难题与一个特殊的数学函数——“神秘函数”S(c)——紧密相关。

神秘函数S(c)的定义：

  • 当c为0时，S(0) = 1。
  • 当c为偶数时，S(c) = S(c/2)。
  • 当c为奇数时，S(c) = S(c-1) + 1。

任务：

编写一个程序，根据输入的正整数α，计算神秘函数S(α)的值。正确解答这道难题将获得通行证，得以进入神秘花园探索知识宝藏。

输入格式：

输入包含一个正整数α（1 ≤ α ≤ 10^6），表示要求解的神秘函数问题中的参数。

输出格式：

输出一个整数，表示神秘函数S(α)的值，即成功解决问题后得到的答案。

解题思路

这道题主要思想就是递归调用，实现了对递推方程的求解问题。

首先，我们定义一个函数，它所实现的功能是返回通过神秘函数运算得到的值。

那么，我们可以分为三个部分：

  1. 当 x=0 时，我们知道通过神秘函数运算得到的值为 1，因此直接返回 1。
  2. 当 x 为偶数时，由于 S(x)=S(x/2)，故我们只需要计算 S(x/2) 的值并返回即可，这时我们再次调用我们定义的函数并以 x/2 为初始值。
  3. 当 x 为奇数时，由于 S(x)=S(x−1)+1，故我们只需要计算S(x−1) 的值并返回 S(x−1)+1 即可，这时我们再次调用我们定义的函数并以 x−1 为初始值。

经过如上过程便可以得出最终结果。

代码语言：javascript
复制
#include <bits/stdc++.h>


// 奇数减一会变成偶数,偶数除以2

// 等价与我们最多使用两次代价使 x 除以 2

// 除以 2 最多 log 次

// O(log)


void solve(const int &Case) {

int x;

std::cin >> x;

std::function<int(int)> S = [&](int x) {

if (x == 0)return 1;

if (x % 2 == 0) {

return S(x / 2);

}

return S(x - 1) + 1;

};

std::cout << S(x) << '\n';

}


int main() {

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);

std::cout.tie(nullptr);

int T = 1;

for (int i = 1; i <= T; i++)solve(i);

return 0;

}

今天就先到这了！！！

#优化#int#递归#函数#算法