GCD Using Recursion: flowchart, algorithm and program
This program reads two integers, a and b, and prints their GCD using a recursive function gcd(a, b). It uses the Euclidean algorithm: the GCD of a and b is the same as the GCD of b and a % b, so the problem shrinks until b becomes 0.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read a.
- Step 3: Read b.
- Step 4: If b == 0, go to step 5; otherwise go to step 6.
- Step 5: Set result = a. Go to step 7.
- Step 6: Set t = a % b; a = b; b = t (recursive call gcd(b, a % b)). Go to step 4.
- Step 7: Print GCD of a and b is result.
- Step 8: Stop.
Program in C, Python and Java
GCD Using Recursion program in C
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a, b;
printf("Enter first number: ");
scanf("%d", &a);
printf("Enter second number: ");
scanf("%d", &b);
printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
return 0;
}GCD Using Recursion program in Python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
print("GCD of", a, "and", b, "is", gcd(a, b))GCD Using Recursion program in Java
import java.util.Scanner;
public class Main {
static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter first number: ");
int a = sc.nextInt();
System.out.print("Enter second number: ");
int b = sc.nextInt();
System.out.println("GCD of " + a + " and " + b + " is " + gcd(a, b));
}
}
Sample input: a = 48, b = 18
Output: Enter first number: Enter second number: GCD of 48 and 18 is 6
How it works
- main() reads a and b, then calls gcd(a, b) inside the printf.
- Base case: if (b == 0) the function returns a, because the GCD of a and 0 is a.
- Recursive case: gcd(b, a % b) calls itself with the old b and the remainder, so the second value gets smaller each time.
- For a = 48, b = 18: gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0), which returns 6.
- That 6 is passed back up through each call unchanged, and printf shows 'GCD of 48 and 18 is 6'.
Dry run (trace table)
| Step | Line | Box | a | b | result | Output |
|---|---|---|---|---|---|---|
| 1 | 9 | Start | ||||
| 2 | 12 | Read a | 48 | Enter first number: | ||
| 3 | 14 | Read b | 48 | 18 | Enter second number: | |
| 4 | 4 | b == 0? | 48 | 18 | ||
| 5 | 6 | t = a % b; a = b; b = t (recursive call gcd(b, a % b)) | 48 | 18 | ||
| 6 | 4 | b == 0? | 18 | 12 | ||
| 7 | 6 | t = a % b; a = b; b = t (recursive call gcd(b, a % b)) | 18 | 12 | ||
| 8 | 4 | b == 0? | 12 | 6 | ||
| 9 | 6 | t = a % b; a = b; b = t (recursive call gcd(b, a % b)) | 12 | 6 | ||
| 10 | 4 | b == 0? | 6 | 0 | ||
| 11 | 5 | result = a | 6 | 0 | 6 | |
| 12 | 15 | Print GCD of a and b is result | 48 | 18 | 6 | GCD of 48 and 18 is 6 |
| 13 | 16 | Stop | 48 | 18 | 6 |
Time and space complexity
Time: O(log(min(a, b))) · Space: O(log(min(a, b))). Each recursive call shrinks the numbers at least by half every two steps, and each call uses one stack frame.
Common mistakes
- Forgetting the base case b == 0, which causes infinite recursion and a crash.
- Calling gcd(a % b, b) or gcd(a, a % b) instead of gcd(b, a % b), which gives wrong results or never ends.
- Returning b instead of a in the base case, which returns 0 instead of the GCD.
Viva questions
Q1. What is the base case in your gcd function, and why is it needed?
The base case is `if (b == 0) return a;` on lines 4-5. It stops the recursion, because when the remainder becomes 0 the current value of a is the GCD. Without it the function would call itself forever.
Q2. What does `a % b` do, and why do we pass it as the second argument?
`%` gives the remainder of a divided by b. The GCD of (a, b) equals the GCD of (b, a % b), so each call replaces the pair with a smaller one. The second number shrinks until it reaches 0.
Q3. Trace gcd(48, 18) step by step.
gcd(48,18) calls gcd(18,12), which calls gcd(12,6), which calls gcd(6,0). Here b is 0, so it returns 6. The GCD is 6.
Q4. What happens if the user enters a smaller number first, for example a = 12 and b = 48?
The first call computes 12 % 48 = 12, so it calls gcd(48, 12). That swaps the two numbers automatically, and the rest runs as normal. The answer is still 12, with one extra call.
Q5. What does your program print if one input is 0, for example a = 0 and b = 5, or a = 7 and b = 0?
For gcd(7, 0), b is 0, so it returns 7. For gcd(0, 5), 0 % 5 = 0, so it calls gcd(5, 0) and returns 5. If both inputs are 0 it returns 0, which is mathematically undefined but is what this code gives.
Q6. What happens with negative inputs, and how would you handle them?
In C, `%` can return a negative remainder, so the result can be negative or not what you expect. For example, gcd(-12, 18) can return -6. To fix it, take the absolute value of a and b before calling gcd, or of the result.
Q7. What is the algorithm called, and what is its time complexity?
It is Euclid's algorithm. It runs in O(log(min(a, b))) time because the remainder at least halves every two steps. The recursion depth is also O(log n), so it uses O(log n) stack space.
Q8. What would change if you wrote this with a loop instead of recursion?
You would use `while (b != 0) { t = b; b = a % b; a = t; }` and return a. The logic and time complexity stay the same, but the stack space drops to O(1) since there are no recursive calls.
Frequently asked questions
How does the Euclidean algorithm find the GCD?
It repeatedly replaces (a, b) with (b, a % b) until b is 0. The remaining value of a is the GCD, since the remainder step never changes the common divisors.
What happens if one of the numbers is 0 in this program?
If b is 0, gcd returns a straight away. If a is 0 and b is not, the first call becomes gcd(b, 0), which returns b, so the answer is still correct.
What is the time complexity of recursive GCD?
It is O(log(min(a, b))), because the remainder shrinks quickly at each step. The recursion depth is also about O(log(min(a, b))).