Homework: GCD + Power

作业: 最大公约数 + 幂

≈ 45 min · python-recursion · Open in WolfCode

Euclid's algorithm (300 BCE) + recursive power. Two short recursions in one file.

Euclid's GCD

Python · runnable

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))    # 6
print(gcd(17, 13))    # 1
print(gcd(10, 0))     # 10

Loading Python runtime (~5 MB, one-time)…

Trace `gcd(48, 18)`

gcd(48, 18) → gcd(18, 12)
gcd(18, 12) → gcd(12,  6)
gcd(12,  6) → gcd( 6,  0)
gcd( 6,  0) → 6                ← base

b shrinks toward 0 each call (because a % b < b), so termination is guaranteed.

Recursive power

Python · runnable

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))    # 1024
print(power(5, 3))     # 125
print(power(7, 0))     # 1

Loading Python runtime (~5 MB, one-time)…

Acceptance criteria

All 9 tests pass
Both gcd and power are recursive
No loops / no ** / no math.gcd / no math.pow

Homework: GCD + Power

Euclid's GCD

Trace gcd(48, 18)

Recursive power

Acceptance criteria

Trace `gcd(48, 18)`