Kotlin Program to Find G.C.D Using Recursion

Finding the Greatest Common Divisor (G.C.D) of two numbers is a common mathematical problem. In this article, we will explore Kotlin Program to Find G.C.D Using Recursion. We will provide three different solutions with examples and outputs.

Introduction

The Greatest Common Divisor (G.C.D) of two or more integers is the largest positive integer that divides each of the integers without a remainder. There are multiple ways to calculate the G.C.D, but using recursion is both elegant and efficient. In this article, we will discuss three different approaches to find the G.C.D using recursion in Kotlin.

Example 1: Using Basic Recursion

1.1 Code

fun gcd(a: Int, b: Int): Int {
    return if (b == 0) a else gcd(b, a % b)
}

fun main(args: Array<String>) {
    val num1 = 56
    val num2 = 98
    val result = gcd(num1, num2)
    println("G.C.D of $num1 and $num2 is $result")
}

1.2 Output

G.C.D of 56 and 98 is 14

1.3 Explanation

In this example, the gcd function uses a simple recursive algorithm. If b is 0, it returns a as the G.C.D. Otherwise, it calls itself with b and the remainder of a divided by b. This is a direct implementation of the Euclidean algorithm.

Example 2: Using Tail Recursion

2.1 Code

tailrec fun gcdTailRec(a: Int, b: Int): Int {
    return if (b == 0) a else gcdTailRec(b, a % b)
}

fun main(args: Array<String>) {
    val num1 = 48
    val num2 = 18
    val result = gcdTailRec(num1, num2)
    println("G.C.D of $num1 and $num2 is $result")
}

2.2 Output

G.C.D of 48 and 18 is 6

2.3 Explanation

The gcdTailRec function is similar to the basic recursion example, but it uses Kotlin’s tailrec modifier. This helps the Kotlin compiler optimize the recursive calls, converting them into iterative loops and preventing stack overflow for large inputs.

Example 3: Using Recursion with Input Validation

3.1 Code

fun gcdWithValidation(a: Int, b: Int): Int {
    require(a > 0 && b > 0) { "Numbers must be positive" }
    return gcd(a, b)
}

fun gcd(a: Int, b: Int): Int {
    return if (b == 0) a else gcd(b, a % b)
}

fun main(args: Array<String>) {
    val num1 = 270
    val num2 = 192
    val result = gcdWithValidation(num1, num2)
    println("G.C.D of $num1 and $num2 is $result")
}

3.2 Output

G.C.D of 270 and 192 is 6

3.3 Explanation

In this example, the gcdWithValidation function first checks if the input numbers are positive. If not, it throws an IllegalArgumentException. This ensures that the inputs are valid before proceeding with the G.C.D calculation using the gcd function defined earlier.

Conclusion

We have discussed three different approaches to find the G.C.D using recursion in Kotlin. Each approach offers a unique way to solve the problem, whether it’s through simple recursion, tail recursion for optimization, or adding input validation for robustness. These examples demonstrate the flexibility and power of recursion in solving common mathematical problems in Kotlin.