欧几里得算法：递归与非递归实现及优化

1. 最大公约数算法概述

在数学和计算机科学中，求两个正整数的最大公约数(GCD)是一个基础但重要的问题。最大公约数是指能够同时整除两个数的最大正整数。这个问题看似简单，但在实际编程中有多种实现方式，每种方式都有其特点和适用场景。

欧几里得算法（又称辗转相除法）是求解GCD最经典的方法，其基本原理是：两个数的最大公约数等于其中较小的数和两数相除余数的最大公约数。这个算法最早出现在欧几里得的《几何原本》中，至今已有2300多年的历史，但仍然是现代计算机科学中最常用的GCD算法。

2. 递归实现解析

2.1 递归算法原理

递归版本的欧几里得算法直接体现了数学定义：

1. 基线条件：当y等于0时，x就是最大公约数
2. 递归条件：否则，计算x除以y的余数，然后用y和余数继续递归

这种实现方式简洁明了，与数学定义高度一致，非常适合教学和理解算法本质。

2.2 代码实现细节

cpp复制#include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std;

int func(int x, int y) {
    if (y == 0) {
        return x;
    }
    else {
        cout << "x "<< x << " " << "y " << y <<" ";
        int yu = x % y;
        cout << "yu " << yu << endl;
        x = y;
        y = yu;
        return func(x, y);
    }
}

int main() {
    int x, y;
    std::cin >> x >> y;
    x = abs(x);
    y = abs(y);
    if (x <= y) {
        swap(x, y);
    }
    int outcome = func(x, y);
    cout << outcome << endl;
    return 0;
}

这段代码有几个值得注意的细节：

1. 使用abs()确保处理的是正整数
2. 通过swap保证x总是较大的数，减少递归次数
3. 添加了调试输出，可以清晰看到每一步的计算过程

提示：在实际项目中，这种调试输出通常会被移除或封装在调试模式下，但在学习阶段保留它们有助于理解算法执行过程。

2.3 递归实现的优缺点

优点：

• 代码简洁，逻辑清晰
• 直接反映数学定义，易于理解
• 适合教学和小规模数据

缺点：

• 递归调用有栈溢出风险（特别是对于极大整数）
• 函数调用开销比循环大
• 调试输出会影响性能

3