Founding Batch Offer ยท HLD ยท LLD ยท System Design at โ‚น799 until 30 Nov

GCD Recursively

Find a GCD with Euclid's recursive algorithm. Students trace remainders, argument swapping, absolute values, and a zero second argument as the base case.

IntermediatePhase 3 - Level 2: Advanced RecursionExample 5 of 10
gcd-recursively.py
1def gcd(a, b):
2 # Base case
3 if b == 0:
4 return a
5
6 # Recursive case (Euclidean algorithm)
7 return gcd(b, a % b)
8
9# Test
10a = int(input("Enter first number: "))
11b = int(input("Enter second number: "))
12result = gcd(abs(a), abs(b))
13print(f"GCD: {result}")

Output

Enter first number: 48
Enter second number: 18
GCD: 6

In this one

  • Apply Euclid's identity
  • Reduce through remainders
  • Handle a zero second argument

How it works

  1. 1

    Pass absolute inputs to gcd.

  2. 2

    Return a when b is zero.

  3. 3

    Otherwise recurse with b and a % b.

Walk through GCD Recursively

gcd(18, 12)

  1. 1.The first recursive pair is (12, 6).
  2. 2.The next pair is (6, 0).
  3. 3.The zero-second-argument base case returns 6.

Edge cases

What is gcd(12, 0)?

What is gcd(12, 0)?

Twelve, returned immediately.

What does this implementation return for gcd(0, 0)?

What does this implementation return for gcd(0, 0)?

Zero, a conventional programming result for that case.

What's going on

gcd(a, b) becomes gcd(b, a % b). The second value gets smaller for nonnegative arguments, eventually reaching zero.

When b is zero, a is returned without attempting modulo by zero. abs makes the public result nonnegative. The call stack stores the short chain of pending returns; this avoids scanning every possible factor as the basic loop version does.

What is gcd(12, 0)? Twelve, returned immediately.

What does this implementation return for gcd(0, 0)? Zero, a conventional programming result for that case.

Quiz

Tap an option. The answer stays hidden until you pick.

Question 1

Which recursive pair is used?

Pick an answer to check it.

Question 2

What is gcd(12, 0)?

Pick an answer to check it.

Questions people ask

What is gcd(12, 0)?

Twelve, returned immediately.

What does this implementation return for gcd(0, 0)?

Zero, a conventional programming result for that case.

Which recursive pair is used?

b, a % b.