C Program to Find GCD Using Recursion

A teacher wants the greatest equal grouping size for eighteen and twelve students. The remainder reduces the grouping problem to a smaller pair.

Euclid’s recursive algorithm replaces (a,b) with (b,a%b), stopping when b is zero and returning a.

Before this exercise, review functions and copied parameters and recursion and stopping cases. The worked program below applies those ideas to this specific problem.

Explain
Explain why recursive gcd uses this sequence of operations.
Trace
Trace the sample values and predict the printed result.
Apply
Call gcd_recursive(18,0) and explain why no division occurs.

Recursive GCD: follow the data

Given data
A teacher wants the greatest equal grouping size for eighteen and twelve students. The remainder reduces the grouping problem to a smaller pair.
Rule
Euclid’s recursive algorithm replaces (a,b) with (b,a%b), stopping when b is zero and returning a.
Observed result
GCD: 6

A guided model of this example. The illustration explains the process; run the complete C program to check its output.

Understand the operation

The nonzero second argument permits remainder division. Its remainder is smaller than that argument, so successive valid calls make progress toward zero.

The base case must run before the remainder operation; otherwise a call with b=0 would attempt division by zero.

Read the complete C program

The input values are written into this complete C17 example so the calculation can be reproduced without an unavailable service. Change the named data, rebuild and compare the actual output with your prediction.

C17 · complete program

#include <stdio.h>
static unsigned gcd_recursive(unsigned a, unsigned b) {
  if (b == 0) return a;
  return gcd_recursive(b, a % b);
}
int main(void) {
  printf("GCD: %u\n", gcd_recursive(18, 12));
  return 0;
}

Expected output

GCD: 6

Run in C compiler →

Follow the values through the code

C17 · code used in this explanation

#include <stdio.h>
static unsigned gcd_recursive(unsigned a, unsigned b) {
  if (b == 0) return a;
  return gcd_recursive(b, a % b);
}
int main(void) {
  printf("GCD: %u\n", gcd_recursive(18, 12));
  return 0;
}

The call pairs are (18,12), (12,6) and (6,0).

The base call returns six; the pending calls return the same gcd result.

Follow the worked calculation

Start with the sample
The call pairs are (18,12), (12,6) and (6,0).
Apply the rule
The base call returns six; the pending calls return the same gcd result.
3
Check the result
GCD: 6
```
GCD: 6
```

A guided model of this example. The illustration explains the process; run the complete C program to check its output.

Try a small variation

C17 · code used in this explanation

#include <stdio.h>
static unsigned gcd_recursive(unsigned a, unsigned b) {
  if (b == 0) return a;
  return gcd_recursive(b, a % b);
}
int main(void) {
  printf("GCD: %u\n", gcd_recursive(18, 12));
  return 0;
}

Call gcd_recursive(18,0) and explain why no division occurs.

Worked answer

The base case returns eighteen immediately. No modulo expression is evaluated for zero as the second argument.

C17 · complete program

#include <stdio.h>
static unsigned gcd_recursive(unsigned a, unsigned b) {
  if (b == 0) return a;
  return gcd_recursive(b, a % b);
}
int main(void) {
  printf("GCD: %u\n", gcd_recursive(18, 0));
  return 0;
}

Expected output

GCD: 18

Run in C compiler →

Recognize the important boundaries

Define a policy for gcd(0,0); this function returns zero, but the classroom grouping interpretation must decide how to report that case.

This function uses unsigned inputs. Handling arbitrary signed inputs needs a safe magnitude conversion, including the minimum signed value.

Choose the answer, then compare the reasoning for every option.

Use the idea independently

Euclid’s recursive algorithm replaces (a,b) with (b,a%b), stopping when b is zero and returning a.

Continue with testing the problem’s boundary cases.

Language reference: WG14 C11 committee draft. These examples use the C17-compatible subset of the explained language features.

Reaching the recap and completing the quizzes are separate milestones.

Next lesson: C Cyclic Swap Using Pointer Parameters →

C Program to Find GCD Using Recursion