当前位置：首页 > news >正文

lxy_蓝桥杯C++系列三_递归

news 2026/6/17 14:31:18

一、递归的介绍

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

递归的两个关键要素：

基本情况(递归终止条件)：递归函数中的一个条件，当满足该条件时，递归终止，避免无限递归。可以理解为直接解决极小规模问题的方法。
递归表达式(递归调用)：递归函数中的语句，用于解决规模更小的子问题，再将子问题的答案合并成为当前问题的答案。

二、递归的实现

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

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

实现过程：

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

设计时需注意的细节：

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

三、递归与循环的比较

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

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

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

四、递归-汉诺塔问题

首先，我们先明确一下题目条件：有三根杆子，我们称它们为 A、B、C。一开始，所有的盘子都放在 A 杆上，从大到小、从下往上堆叠。
目标：把所有盘子从 A 杆移到 C 杆，
并且：一次只能移动一个盘子；大盘子不能放在小盘子上面。
汉诺塔之所以适合用递归来解决，是因为它可以层层分解成相同形式的子问题。

【题目拆解】
我们想象一下：如果有 N 个盘子，我们可以把它分成两组：
最底下的第 N 个盘子（最大的那个）；上面的 N-1 个盘子。
那么，移动 N 个盘子的过程，可以分解为三个大步骤：先把上面的 N-1 个盘子从 A 移到 B（此时 C 作为辅助杆）；再把最大的那个盘子从 A 移到 C；最后把 B 上的 N-1 个盘子从 B 移到 C（此时 A 作为辅助杆）。

这样一来，移动 N 个盘子的问题就变成了两次移动 N-1 个盘子的问题，再加上一次直接移动最大盘的操作。

【递归函数设计】
我们可以定义一个函数：

void hanoi(char A, char B, char C, int n);

它的意思也就是说：借助 B 杆，把 A 杆上的 n 个盘子移动到 C 杆。
那么我们接下来递归的实现就更加直观了：

void hanoi(char A, char B, char C, int n) {if (n == 1) {// 只有一个盘子时，直接移动sing_move(A, C, n);return;}// 1. 把上面 n-1 个从 A 移到 B（C 作为辅助）hanoi(A, C, B, n - 1);// 2. 把最大的盘子从 A 移到 Csing_move(A, C, n);// 3. 把 B 上的 n-1 个盘子从 B 移到 C（A 作为辅助）hanoi(B, A, C, n - 1);
}

然后这里的 sing_move(A, C, n) 我们可以把它理解为打印一步移动操作，比如 "A → C"。

五、递归四要点