GCD(8, 12) = 4

GCD(5, 8) = 1

```
function euclid(m, k) {
if (k == 0) {
return m;
} else {
return euclid(k, m % k);
}
}
```

```
function euclid(m, k) {
if (k == 0) {
return m;
} else {
return euclid(k, m % k);
}
}
```

```
euclid(8, 5) // 8 = 1 × 5 + 3
== euclid(5, 3) // 5 = 1 × 3 + 2
== euclid(3, 2) // 3 = 1 × 2 + 1
== euclid(2, 1) // 2 = 1 × 1 + 0
== euclid(1, 0)
== 1
```

`■ ■ ■ ■ ■ □ □ □ □ □ □ □ □ ← euclid(8, 5) `

`■□ ■□ ■□ ■□ ■□ □ □ □ ← 8 = 1 × 5 + 3`

`■□□ ■□□ ■□□ ■□ ■□ ← 5 = 1 × 3 + 2`

`■□□■□ ■□□■□ ■□□ ← 3 = 1 × 2 + 1`