🏺 Did the Ancient Greeks Know Recursion?

 

From Euclid to Algorithms, and Back Again

When we talk about recursion today, we usually think of code. A function that calls itself, elegant, efficient, and, if you’re not careful, infinite.

But long before computers existed, the Ancient Greeks were already reasoning recursively. They just didn’t call it that.

---

🌀 Recursion Before Computers

Recursion means solving a problem by reducing it to smaller instances of itself and stopping when you reach something simple enough to handle directly.

The Greeks didn’t have “functions,” but they did have processes that repeated their own logic step after step. And the clearest example comes from Euclid, around 300 BCE, in his Elements, Book VII.

There, he describes how to find the greatest common divisor (gcd) of two integers -the largest number that divides both without remainder.

Today, we call this Euclid’s algorithm, and it’s arguably the oldest recursive algorithm in recorded history.

---

🧮 Euclid’s Algorithm (as Euclid Told It)

Euclid states:

If one number divides another, it is the greatest common measure of them. Otherwise, take away from the greater number its smaller multiple that is contained in it, and continue with the remainder and the smaller number until no remainder is left. The last nonzero remainder is the greatest common divisor.

Let’s translate this into modern notation.

Suppose we have two positive integers a and b, with a ≥ b.

1. If b divides a exactly, then gcd(a, b) = b.
2. Otherwise, compute the remainder r = a mod b.
3. Replace (a, b) with (b, r).
4. Repeat until the remainder is 0.
5. The last nonzero remainder is gcd(a, b).

That’s recursion in its purest form:

gcd(a, b) = gcd(b, a mod b), until the second argument becomes 0.

---

✏️ Example: gcd(1071, 462)

Let’s see Euclid’s algorithm step by step:

• 1071 ÷ 462 = 2 remainder 147 → gcd(1071, 462) = gcd(462, 147)
• 462 ÷ 147 = 3 remainder 21 → gcd(462, 147) = gcd(147, 21)
• 147 ÷ 21 = 7 remainder 0 → gcd(147, 21) = 21

Hence gcd(1071, 462) = 21.

If we were to write this recursively:

gcd(a, b):

if b = 0:

return a

else:

return gcd(b, a mod b)

Each call makes the problem smaller. The same reasoning, applied repeatedly, until the process “bottoms out.”

---

🧩 Why It Works (Proof of Correctness)

Let’s prove Euclid’s algorithm is correct, not by authority, but by logic.

Lemma:

If a = b·q + r, then gcd(a, b) = gcd(b, r).

Proof: Any integer that divides both a and b must also divide r = a – b·q. Conversely, any integer that divides both b and r must also divide a = b·q + r. Thus, they share the same set of common divisors, so their greatest common divisor is equal. ✅

Now, every iteration replaces (a, b) with (b, r), which has a smaller second argument. Eventually, r = 0, and gcd(a, 0) = a. Therefore, the algorithm terminates and returns the correct gcd.

That’s a complete mathematical proof and also a recursive correctness proof.

---

🧠 Recursion Without Symbols

The Greeks didn’t express recursion as we do, because they didn’t separate process from proof. For them, each step of the algorithm was the reasoning a geometric, embodied logic.

When Euclid subtracts “the smaller from the larger,” he’s not looping or calling a function; he’s demonstrating that structure repeats until the form becomes indivisible, until we reach what the Greeks called arithmos protos, the fundamental unit of measure.

This is recursion in philosophy as much as in mathematics: reduction until essence remains.

---

📘 From Euclid to Riemann

In The Riemann Hypothesis Revealed: A Comprehensive Guide Through Complex Analysis, I discuss how similar recursive ideas appear in modern analysis, especially in analytic continuation, where a function defines itself beyond its original domain by referring to earlier values. The Riemann Hypothesis Revealed

This is the analytic descendant of Euclid’s method: reduce, extend, repeat, until the pattern reaches the infinite.

---

⚖️ Final Thought

The Ancient Greeks didn’t name recursion. They discovered it geometrically, philosophically, and algorithmically.

We only gave it a syntax.