第7章：递归（Rekursion）
学习目标
理解递归的基本概念与工作原理
掌握递归函数的设计方法
了解递归与迭代的区别与性能差异
熟悉递归在算法设计中的应用
1. 递归定义
递归程序：直接或间接调用自身的程序
递归函数/算法：通过解决更小规模的相同问题来解决问题
关键要素：
递归步骤（Rekursionsschritt）：将问题分解为更小的子问题
基础情况（Basisfall / Rekursionsverankerung）：终止条件，防止无限递归
2. 数学中的递归示例
阶乘（Fakultät）
定义：n! = n × (n-1) × (n-2) × ... × 1
基础情况：0! = 1
递归步骤：n! = n × (n-1)!
C++ 实现
Cpp
深色版本
long fakultaet(int n) {
    if (n == 0) return 1;           // 基础情况
    return n * fakultaet(n - 1);    // 递归步骤
}
使用 long 类型避免整数溢出（如 20! ≈ 2.43×10¹⁸）

最大公约数（ggT）——欧几里得算法
Cpp
深色版本
int ggt(int a, int b) {
    if (b == 0) return a;           // 基础情况
    return ggt(b, a % b);           // 递归步骤
}
执行过程：

深色版本
ggT(7856, 5616)
→ ggT(5616, 2240)
→ ggT(2240, 1136)
→ ...
→ ggT(16, 0) → 返回 16
3. 递归应用：绘制刻度尺
问题描述
绘制一个刻度尺，中间刻度最长，两侧刻度依次减半。

递归思路
将区间分为左右两半
递归绘制左侧刻度尺（高度减1）
绘制中间刻度
递归绘制右侧刻度尺（高度减1）
C++ 实现
Cpp
深色版本
void zeichne_marke(int position, int h) {
    while (h--) cout << '-';
    cout << endl;
}

void lineal(int li, int re, int h) {
    int m = (li + re) / 2;
    if (h > 0) {
        lineal(li, m, h - 1);       // 左侧
        zeichne_marke(m, h);        // 中间
        lineal(m, re, h - 1);       // 右侧
    }
}
位运算技巧：1 << n 等价于 2^n，用于设置右边界

4. 递归 vs. 迭代
阶乘的迭代实现
Cpp
深色版本
long fakultaetIter(int n) {
    long wert = 1;
    while (n > 0) wert *= n--;
    return wert;
}
性能对比
递归：代码简洁，但每次调用需压栈（参数、返回地址），开销大
迭代：通常更高效，无函数调用开销
实测结果（n=30）：

递归耗时：3.11e-07 秒
迭代耗时：1.47e-07 秒
结论：两者都很快，但迭代约快一倍

5. 递归设计要点
基础情况必须存在且可达，否则导致无限递归
每次递归调用应处理更小的子问题，确保最终到达基础情况
并非所有问题都适合递归，有时迭代更高效或更简单
6. 总结
特性	递归	迭代
代码简洁性	高（问题自然表达）	低（需显式循环）
内存开销	高（栈空间）	低
性能	较低（函数调用开销）	较高
适用场景	分治、回溯、树遍历等	简单循环、性能敏感
原则：任何迭代算法都可改写为递归，反之亦然。选择取决于问题特性和性能需求。

```cpp
#include<bits/stdc++.h>
using namespace std;

// f(n) = f(n-1) * n 
// f(1) = f(0) * 1

int f(int n)
{
	if(n==1) return 1;
	int a = f(n-1);
	return a * n;
}

int fib(int n)
{
	if(n == 1 || n == 2) return 1; //基础条件 
	return fib(n-1) + fib(n-2);
}

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a%b) ; //辗转相余 
}

int gcd_(int a,int b){
	while(a>0 && b>0){
		int r = a % b;
		//迭代
		a = b; //准备下一轮 
		b = r; 
	}
	return max(a,b);
}

int main(){
	cout << gcd_(999999999, 2) ;
	return 0;
}
```

第7章：递归（Rekursion）学习目标理解递归的基本概念与工作原理掌握递归函数的设计方法了解递归与迭代的区别与性能差异熟悉递归在算法设计中的应用 1. 递归定义递归程序：直接或间接调用自身的程序递归函数/算法：通过解决更小规模的相同问题来解决问题关键要素：递归步骤（Rekursionsschritt）：将问题分解为更小的子问题基础情况（Basisfall / Rekursionsverankerung）：终止条件，防止无限递归 2. 数学中的递归示例阶乘（Fakultät）定义：n! = n × (n-1) × (n-2) × ... × 1 基础情况：0! = 1 递归步骤：n! = n × (n-1)! C++ 实现 Cpp 深色版本 long fakultaet(int n) { if (n == 0) return 1; // 基础情况 return n * fakultaet(n - 1); // 递归步骤 } 使用 long 类型避免整数溢出（如 20! ≈ 2.43×10¹⁸）

最大公约数（ggT）——欧几里得算法 Cpp 深色版本 int ggt(int a, int b) { if (b == 0) return a; // 基础情况 return ggt(b, a % b); // 递归步骤 } 执行过程：

深色版本 ggT(7856, 5616) → ggT(5616, 2240) → ggT(2240, 1136) → ... → ggT(16, 0) → 返回 16 3. 递归应用：绘制刻度尺问题描述绘制一个刻度尺，中间刻度最长，两侧刻度依次减半。

递归思路将区间分为左右两半递归绘制左侧刻度尺（高度减1）绘制中间刻度递归绘制右侧刻度尺（高度减1） C++ 实现 Cpp 深色版本 void zeichne_marke(int position, int h) { while (h--) cout << '-'; cout << endl; }

void lineal(int li, int re, int h) { int m = (li + re) / 2; if (h > 0) { lineal(li, m, h - 1); // 左侧 zeichne_marke(m, h); // 中间 lineal(m, re, h - 1); // 右侧 } } 位运算技巧：1 << n 等价于 2^n，用于设置右边界

递归 vs. 迭代阶乘的迭代实现 Cpp 深色版本 long fakultaetIter(int n) { long wert = 1; while (n > 0) wert *= n--; return wert; } 性能对比递归：代码简洁，但每次调用需压栈（参数、返回地址），开销大迭代：通常更高效，无函数调用开销实测结果（n=30）：

递归耗时：3.11e-07 秒迭代耗时：1.47e-07 秒结论：两者都很快，但迭代约快一倍

递归设计要点基础情况必须存在且可达，否则导致无限递归每次递归调用应处理更小的子问题，确保最终到达基础情况并非所有问题都适合递归，有时迭代更高效或更简单
总结特性递归迭代代码简洁性高（问题自然表达）低（需显式循环）内存开销高（栈空间）低性能较低（函数调用开销）较高适用场景分治、回溯、树遍历等简单循环、性能敏感原则：任何迭代算法都可改写为递归，反之亦然。选择取决于问题特性和性能需求。

#include<bits/stdc++.h>
using namespace std;

// f(n) = f(n-1) * n 
// f(1) = f(0) * 1

int f(int n)
{
    if(n==1) return 1;
    int a = f(n-1);
    return a * n;
}

int fib(int n)
{
    if(n == 1 || n == 2) return 1; //基础条件 
    return fib(n-1) + fib(n-2);
}


int gcd(int a, int b)
{
    if(b == 0) return a;
    else return gcd(b, a%b) ; //辗转相余 
}

int gcd_(int a,int b){
    while(a>0 && b>0){
        int r = a % b;
        //迭代
        a = b; //准备下一轮 
        b = r; 
    }
    return max(a,b);
}


int main(){
    cout << gcd_(999999999, 2) ;
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com