# 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`.