十堰专业网站设计制作,可以制作试卷的app,wordpress自定义编辑器,定制网站模板站递归的介绍
概念:递归是指函数直接或间接调用自身的过程。 解释递归的两个关键要素: 基本情况(递归终止条件):递归函数中的一个条件#xff0c;当满足该条件时#xff0c;递归终止#xff0c;避免无限递归。可以理解为直接解决极小规模问题的方法。递归表达式(递归调用):递…递归的介绍
概念:递归是指函数直接或间接调用自身的过程。 解释递归的两个关键要素: 基本情况(递归终止条件):递归函数中的一个条件当满足该条件时递归终止避免无限递归。可以理解为直接解决极小规模问题的方法。递归表达式(递归调用):递归函数中的语句用于解决规模更小的子问题再将子问题的答案合并成为当前问题的答案。
递归如何实现
递归函数的基本结构如下:
返回类型 函数名(参数列表){基本情况(递归终止条件)
if(满足终止条件){返回终止条件下的结果递归表达式(递归调用)
}
else if{将问题分解为规模更小的子问题使用递归调用解决子问题返回子问题的结果
}
实现过程:
将大问题分解为规模更小的子问题。使用递归调用解决每个子问题。通过递归终止条件来结束递归。
设计时需注意的细节:
确保递归一定能到递归出口避免无限递归这可能导致TLE(超时)、MLE(超内存)、或RE(运行错误)考虑边界条件有时候递归出口不止一个。避免不必要的重复计算尽可能优化递归函数的性能(例如使用记忆化)。
递归和循环的比较
递归的特点:
直观、简洁易于理解和实现适用于问题的规模可以通过递归调用不断减小的情况。可以处理复杂的数据结构和算法如树和图的遍历。(线段树)存在栈溢出风险(栈空间一般只有8MB所以递归层数不宜过深一般不超过1e6层)。
循环的特点:
1.直接控制流程效率较高。(常数小)2.适用于问题的规模没有明显的缩减或者需要特定的迭代次数。(二元组)3.适合处理大部分的动态规划问题
在部分情况下递归和循环可以相互转化。(DFS)
例题:
一、斐波那契数列带备忘录的递归
已知F(1)F(2) 1;n3时F(n)F(n-1)F(n-2) 输入n求F(n)n100000结果对1e97取模
如果直接使用递归难以算出结果需要优化
时间复杂度为
#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;
} 优化方法带备忘录的递归
时间复杂度为
#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记录下数字每一位上的数字是多少然后枚举当前位上的数字递归的向下去求方案数并求和即可。
#includebits/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(α)的值即成功解决问题后得到的答案。 解题思路
这道题主要思想就是递归调用实现了对递推方程的求解问题。
首先我们定义一个函数它所实现的功能是返回通过神秘函数运算得到的值。
那么我们可以分为三个部分
当 x0 时我们知道通过神秘函数运算得到的值为 1因此直接返回 1。当 x 为偶数时由于 S(x)S(x/2)故我们只需要计算 S(x/2) 的值并返回即可这时我们再次调用我们定义的函数并以 x/2 为初始值。当 x 为奇数时由于 S(x)S(x−1)1故我们只需要计算S(x−1) 的值并返回 S(x−1)1 即可这时我们再次调用我们定义的函数并以 x−1 为初始值。
经过如上过程便可以得出最终结果。
#include bits/stdc.h// 奇数减一会变成偶数,偶数除以2
// 等价与我们最多使用两次代价使 x 除以 2
// 除以 2 最多 log 次
// O(log)void solve(const int Case) { int x;std::cin x;std::functionint(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;
} 今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
