递归算法详解：从基础到递归+暴解

"这篇文档详细介绍了递归和暴力求解这两种算法思想，涵盖了它们的定义、特点、应用场景以及代码示例。文档作者刘帅坤来自河南理工大学ACM协会，创作时间为2018年8月2日。" **递归** 递归是一种编程技术，通过在函数或子过程中直接或间接地调用自身来解决问题。递归算法的特点包括： 1. **自调用**：递归函数在执行时会调用自身，形成一种自我复制的行为。 2. **递归出口**：为了确保递归能够终止，必须设定一个明确的递归结束条件，即当满足某种特定情况时，不再进行递归调用。 3. **规模缩小**：每次递归调用通常将问题规模减小，直到达到可以直接解答的规模。 4. **效率问题**：虽然递归算法通常简洁易懂，但由于需要维护调用栈，可能导致较高的时间和空间复杂度，尤其在递归层次过深时可能引发栈溢出。 **递归算法的要求** 递归算法的“重复”包含三个关键要素： 1. **规模减小**：每次调用应使问题规模减小，通常是减半。 2. **前后关联**：相邻两次递归调用间存在紧密联系，前一次的输出通常作为后一次的输入。 3. **递归终止**：在问题足够小到可以直接求解时不进行递归调用，以防止无限递归。 **贪心算法** 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。然而，贪心算法并不保证总是得到全局最优解，只适用于问题的最优解可以通过局部最优解得出的情况。 **简单枚举** 简单枚举，又称暴力求解，是一种基础的解决问题的方法，它尝试穷举所有可能的解决方案，并检查每个解是否满足问题的条件。这种方法在问题规模较小或没有更高效算法的情况下可行，但随着问题规模的增长，其效率会急剧下降。 **算法示例** 文档中给出了计算阶乘的递归算法实现，其时间复杂度为O(logn)，代码如下： ```cpp #include<cstdio> int solve(int n) { return n == 0 ? 1 : solve(n - 1) * n; } int main() { int n; while (scanf("%d", &n) != EOF) printf("%d\n", solve(n)); } ``` 这个程序计算给定整数n的阶乘，使用递归方式实现，当n等于0时返回1，否则返回n乘以n-1的阶乘。 递归和暴力求解是两种基本的算法思想，各有优缺点。在实际问题中，需要根据问题性质和规模选择合适的算法策略。递归常用于分治、树形结构和图遍历等问题，而贪心和暴力求解则适用于特定类型的问题。