Code Logo

Greatest Common Divisor Recursively

Published at19 Apr 2026
Created by
Recursion Medium 13 views
Like0

Have you ever had to divide a large batch of items into equal groups? Finding the Greatest Common Divisor (GCD) is exactly that—it is the largest possible number that divides two integers without leaving any remainder.

Imagine you have 48 blue marbles and 18 red marbles. If you want to put them into bags where every bag has the same number of marbles and there are no marbles left over, the largest number of marbles per bag would be 6. That is the power of the GCD.

Instead of trying every possible divisor, we can use a clever mathematical trick called the Euclidean algorithm. The idea is that the GCD of two numbers also divides their difference, or more simply, gcd(a, b) is the same as gcd(b, a MOD b). We just keep repeating this until one number hits zero, and the remaining number is our answer.

Learn about our pseudocode specification
Guide

Example Input & Output

Example 1
Input
a = 21, b = 14
Output
7
Explanation

7 divides both numbers exactly.

Example 2
Input
a = 9, b = 28
Output
1
Explanation

These numbers share no common divisor larger than 1.

Example 3
Input
a = 48, b = 18
Output
6
Explanation

The largest integer that divides both 48 and 18 is 6.

Algorithm Flow

Recommendation Algorithm Flow for Greatest Common Divisor Recursively
Recommendation Algorithm Flow for Greatest Common Divisor Recursively

Solution Approach

The Euclidean algorithm is a classic example of recursion because the solution to a large problem depends on the solution to a slightly smaller version of the same problem.

To build this in pseudocode, we start with a base case: if the second number b is 0, we stop and return a. That is our answer. If b is not zero, we simply call the function again, but this time we pass b as the first argument and the remainder of a divided by b as the second.

function gcd(a, b)
   if b = 0 then
      return a
   else
      return gcd(b, a MOD b)
   endif
endfunction

By using MOD, the numbers shrink incredibly fast. For example, computing gcd(48, 18) only takes a few steps: it goes to gcd(18, 12), then gcd(12, 6), and finally gcd(6, 0). It is efficient, elegant, and much faster than counting one by one.

Best Answers

Pseudocode - Approach 1
function gcd(a: integer, b: integer) -> integer
dictionary
algorithm
   if b = 0 then
      return a
   else
      return gcd(b, a MOD b)
   endif
endfunction

program greatest_common_divisor_recursive
dictionary
   a, b: integer
algorithm
   input(a, b)
   output(gcd(a, b))
endprogram