🚀 在数学领域中，扩展欧几里德算法是一种重要的工具，用于解决线性方程组。它不仅能够找到两个整数的最大公约数（GCD），还能找到这两个数之间的线性组合系数。这在密码学、计算机科学等领域有着广泛的应用。

🔧 本文将深入探讨如何用递归和非递归两种方法实现扩展欧几里德算法，并通过简单的例子来证明其正确性。首先，我们来看递归实现：

💡 递归实现：

```python

def extended_gcd_recursive(a, b):

if b == 0:

return a, 1, 0

else:

gcd, x, y = extended_gcd_recursive(b, a % b)

return gcd, y, x - (a // b) y

```

🌈 这个方法利用了递归调用，简洁且直观地实现了算法的核心逻辑。

🔨 接着，我们探讨非递归实现：

💡 非递归实现：

```python

def extended_gcd_non_recursive(a, b):

old_r, r = a, b

old_s, s = 1, 0

old_t, t = 0, 1

while r != 0:

quotient = old_r // r

old_r, r = r, old_r - quotient r

old_s, s = s, old_s - quotient s

old_t, t = t, old_t - quotient t

return old_r, old_s, old_t

```

🌈 非递归版本通过循环结构逐步逼近最终解，同样能够高效地解决问题。

🔍 无论是递归还是非递归实现，扩展欧几里德算法都能为我们提供强大的工具，帮助我们在各种场景下快速找到问题的答案。