Let's trace through the GCD algorithm step-by-step for the call GCD(20, 12) using top-down evaluation. The algorithm uses the Euclidean method to compute the greatest common divisor (GCD).

---

Initial Call: GCD(20, 12)

1. Step 1:

   • Input: $m = 20$, $n = 12$
   • Condition: $n \neq 0$
   • $20 \mod 12 = 8$ (since $20 \div 12 = 1$ with a remainder of $8$)
   • Recursive Call: GCD(12, 8)

2. Step 2:

   • Input: $m = 12$, $n = 8$
   • Condition: $n \neq 0$
   • $12 \mod 8 = 4$ (since $12 \div 8 = 1$ with a remainder of $4$)
   • Recursive Call: GCD(8, 4)

3. Step 3:

   • Input: $m = 8$, $n = 4$
   • Condition: $n \neq 0$
   • $8 \mod 4 = 0$ (since $8 \div 4 = 2$ with no remainder)
   • Recursive Call: GCD(4, 0)

4. Step 4:

   • Input: $m = 4$, $n = 0$
   • Condition: $n = 0$
   • Return: $4$

---

Conclusion

The greatest common divisor of 20 and 12 is 4.

---

Final Evaluation Steps Summary:

1. GCD(20, 12) → GCD(12, 8)
2. GCD(12, 8) → GCD(8, 4)
3. GCD(8, 4) → GCD(4, 0)
4. GCD(4, 0) = 4

The final result is 4.

---

Do you want a detailed explanation of the Euclidean algorithm or have any questions?

Related Questions:

1. How does the Euclidean algorithm work in general?
2. What is the time complexity of the Euclidean algorithm?
3. Can you demonstrate the Euclidean algorithm for GCD(48, 18)?
4. How does the modulo operation function in this algorithm?
5. How can the Euclidean algorithm be implemented in a programming language like Python?

Tip:

The Euclidean algorithm is one of the most efficient ways to compute the greatest common divisor and forms the foundation of many number-theoretic applications.