Swift Program to Find Greatest Common Divisor (GCD) using Recursion

Swift – Find Greatest Common Divisor (GCD) using Recursion

In this tutorial, we will learn how to find the Greatest Common Divisor (GCD) of two numbers using recursion in Swift. We will understand the concept of GCD, write an algorithm, and implement the solution step by step with a complete Swift program and output.

---

What is GCD?

The Greatest Common Divisor (GCD) of two integers is the largest number that divides both integers without leaving a remainder. For example:

• GCD of 12 and 8 is 4 because 4 is the largest number that divides both 12 and 8.
• GCD of 60 and 48 is 12 because 12 is the largest number that divides both 60 and 48.

We will use the Euclidean algorithm to find the GCD recursively.

---

Algorithm to Find GCD Using Recursion

1. Base Case: If the second number b is 0, return the first number a as the GCD.
2. Recursive Case: Call the function with a = b and b = a % b.

This algorithm ensures that the problem is divided into smaller subproblems, reducing b until it becomes 0.

---

Step-by-Step Implementation in Swift

1. Define the Base Case

Create a function that returns the first number when the second number is 0:

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a // Base case: GCD is a when b is 0
    }
    return 0 // Placeholder for the recursive case
}

2. Add the Recursive Case

Implement the recursive logic using the formula gcd(a, b) = gcd(b, a % b):

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a // Base case
    }
    return gcd(b, a % b) // Recursive case
}

Explanation:

if b == 0: Returns a as the GCD when b becomes 0.

gcd(b, a % b): Calls the function recursively with the second number b and the remainder of a % b.

3. Test the Function

Let’s test the function with some example inputs:

// Test cases
print("GCD of 12 and 8: \(gcd(12, 8))")  // Output: 4
print("GCD of 60 and 48: \(gcd(60, 48))") // Output: 12
print("GCD of 7 and 13: \(gcd(7, 13))")   // Output: 1
print("GCD of 0 and 5: \(gcd(0, 5))")     // Output: 5

---

Complete Swift Program

Here’s the complete Swift program to find the Greatest Common Divisor (GCD) of two numbers using recursion:

main.swift

import Foundation

// Function to calculate GCD using recursion
func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a // Base case
    }
    return gcd(b, a % b) // Recursive case
}

// Test cases
print("GCD of 12 and 8: \(gcd(12, 8))")  // Output: 4
print("GCD of 60 and 48: \(gcd(60, 48))") // Output: 12
print("GCD of 7 and 13: \(gcd(7, 13))")   // Output: 1
print("GCD of 0 and 5: \(gcd(0, 5))")     // Output: 5

Output:

GCD of 12 and 8: 4
GCD of 60 and 48: 12
GCD of 7 and 13: 1
GCD of 0 and 5: 5
Program ended with exit code: 0

Xcode Screenshot