Python Code Example: greatest common divisor (recursive)

The code calculates the greatest common divisor (GCD) of two integers a and b using the Euclidean algorithm. The gcd function is a recursive function that returns the GCD of two numbers by subtracting the smaller number from the larger number until one of them is zero. The GCD of the two numbers is then returned.

Code Example

def gcd(a, b):
    if a == 0:
      return b
    elif b == 0:
      return a
    elif a > b:
      return gcd(a - b, b)
    else:
      return gcd(a, b - a)


a, b = 200, 60

print("Greatest common divisor is: " + str(gcd(a, b)))

Output

Greatest common divisor is: 20

Code Explanation

Function gcd(a, b)

def gcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    elif a > b:
        return gcd(a - b, b)
    else:
        return gcd(a, b - a)

• Purpose: This function calculates the GCD of two integers a and b.
• Parameters: The function takes two parameters:
  • a: The first integer.
  • b: The second integer.
• Base Cases:
  • if a == 0: If a is 0, the GCD is b. This is because the GCD of 0 and any number b is b.
  • elif b == 0: If b is 0, the GCD is a. Similarly, the GCD of 0 and any number a is a.
• Recursive Cases:
  • elif a > b: If a is greater than b, the function calls itself with a - b and b. This step reduces the value of a by subtracting b from it.
  • else: If b is greater than or equal to a, the function calls itself with a and b - a. This step reduces the value of b by subtracting a from it.

This process continues recursively until one of the base cases is met, effectively reducing the problem size at each step.

Main Program

a, b = 200, 60

• Variable Initialization: Two variables a and b are initialized with the values 200 and 60 respectively.

print("Greatest common divisor is: " + str(gcd(a, b)))

• Function Call and Output:
  • The gcd function is called with a and b as arguments.
  • The result, which is the GCD of 200 and 60, is converted to a string and concatenated with the message “Greatest common divisor is: “.
  • This message is printed to the console.

Example Execution

For gcd(200, 60), the function will perform the following steps:

1. First Call: gcd(200, 60)
   • Since 200 > 60, it calls gcd(200 - 60, 60) which is gcd(140, 60).
2. Second Call: gcd(140, 60)
   • Since 140 > 60, it calls gcd(140 - 60, 60) which is gcd(80, 60).
3. Third Call: gcd(80, 60)
   • Since 80 > 60, it calls gcd(80 - 60, 60) which is gcd(20, 60).
4. Fourth Call: gcd(20, 60)
   • Since 60 > 20, it calls gcd(20, 60 - 20) which is gcd(20, 40).
5. Fifth Call: gcd(20, 40)
   • Since 40 > 20, it calls gcd(20, 40 - 20) which is gcd(20, 20).
6. Sixth Call: gcd(20, 20)
   • Since 20 == 20, it calls gcd(20, 20 - 20) which is gcd(20, 0).
7. Seventh Call: gcd(20, 0)
   • Since b == 0, it returns a, which is 20.