Go Program to Find GCD Using Recursion

You can find the GCD of two numbers in Go using recursion with the function func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a % b) } which calls itself until the remainder is zero.

Examples

Input48, 18

Output6

Input100, 25

Output25

Input7, 3

Output1

How to Think About It

To find the GCD using recursion, think of the problem as repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the GCD. This uses the idea that GCD(a, b) = GCD(b, a % b).

Algorithm

1

Take two numbers as input.

2

Check if the second number is zero.

3

If yes, return the first number as the GCD.

4

If no, call the function again with the second number and the remainder of first number divided by second number.

5

Repeat until the second number becomes zero.

Code

go

package main

import "fmt"

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func main() {
    fmt.Println(gcd(48, 18))
}

Output

6

Dry Run

Let's trace gcd(48, 18) through the code

1

Initial call

gcd(48, 18) checks if 18 == 0 (false), calls gcd(18, 48 % 18)

2

Second call

gcd(18, 12) checks if 12 == 0 (false), calls gcd(12, 18 % 12)

3

Third call

gcd(12, 6) checks if 6 == 0 (false), calls gcd(6, 12 % 6)

4

Fourth call

gcd(6, 0) checks if 0 == 0 (true), returns 6

5

Return chain

Returns 6 back through all previous calls

Call	a	b	a % b	Return Value
1	48	18	12	calls gcd(18,12)
2	18	12	6	calls gcd(12,6)
3	12	6	0	calls gcd(6,0)
4	6	0	-	returns 6

Why This Works

Step 1: Base Case

The function stops calling itself when the second number b becomes zero, returning the first number a as the GCD.

Step 2: Recursive Call

If b is not zero, the function calls itself with b and the remainder of a % b, reducing the problem size.

Step 3: Mathematical Principle

This works because the GCD of two numbers also divides their remainder, so the problem simplifies until the remainder is zero.

Alternative Approaches

Iterative approach

go

package main

import "fmt"

func gcdIterative(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func main() {
    fmt.Println(gcdIterative(48, 18))
}

This uses a loop instead of recursion, which can be easier to understand and avoids function call overhead.

Using Euclid's subtraction method

go

package main

import "fmt"

func gcdSubtraction(a, b int) int {
    if a == b {
        return a
    }
    if a > b {
        return gcdSubtraction(a-b, b)
    }
    return gcdSubtraction(a, b-a)
}

func main() {
    fmt.Println(gcdSubtraction(48, 18))
}

This method uses subtraction instead of modulus but can be slower for large numbers.

Complexity: O(log(min(a,b))) time, O(log(min(a,b))) space

Time Complexity

Each recursive call reduces the problem size roughly by the remainder, which decreases quickly, leading to logarithmic time complexity.

Space Complexity

Recursive calls add to the call stack, so space complexity is proportional to the number of calls, which is logarithmic.

Which Approach is Fastest?

The recursive modulus method is generally faster and cleaner than subtraction. Iterative avoids recursion overhead but is similar in speed.

Approach	Time	Space	Best For
Recursive modulus	O(log(min(a,b)))	O(log(min(a,b)))	Clean code, teaching recursion
Iterative modulus	O(log(min(a,b)))	O(1)	Performance-critical code avoiding recursion
Subtraction method	O(min(a,b))	O(min(a,b))	Simple logic but slower for large inputs