CodeBhavya
Program navigation

C PROGRAM • FUNCTIONS & RECURSION

Find GCD of Two Numbers Using Recursion

Use Euclid's algorithm to repeatedly replace two numbers with the smaller problem gcd(b, a % b) until the remainder becomes zero.

Intermediate Recursive function Interactive trace
Review these lessons if required: C Functions C Recursion Modulus Operator

PROBLEM UNDERSTANDING

What should the program do?

Read two positive integers and print their greatest common divisor. The GCD is the largest positive integer that divides both numbers without leaving a remainder.

Sample input 
48
18
Sample output 
Enter two positive integers: 48 18
GCD of 48 and 18 is 6.

C PROGRAM

GCD using recursion

gcd_recursion.c
Copy & open compiler 

          

        


        

          

            

              
INTERACTIVE LEARNING

              Debug the recursive execution
              
Change the inputs, start debugging and follow the call stack.

            

            

              
              
              
              
              
              
            

          


          

            
            
            
          


          

            


            

              

                
CURRENT STEP

                
Enter two values and select Start.

              


              

                
VARIABLES

                

                  
ScopeNameValue

                  
Not started

                

              


              

                
CALL STACK

                
empty

              


              

                
PROGRAM OUTPUT

                
Waiting to run…

              

            

          


          

            0%
            Step 0 of 0
          

        


        

          
PROGRAM EXPLANATION

          
How the recursive solution works

          
    
            
  1. main() reads two positive integers.
    2. 
            
  2. gcd(a, b) checks whether b is zero.
    3. 
            
  3. If b == 0, the current value of a is the GCD.
    4. 
            
  4. Otherwise, the function calls gcd(b, a % b).
    5. 
            
  5. Each call creates a smaller remainder, so the recursion eventually reaches zero.
    6. 
          


          
Dry run for 48 and 18

          
gcd(48, 18)
→ gcd(18, 12)
→ gcd(12, 6)
→ gcd(6, 0)
→ return 6

        


        

          
EFFICIENCY

          
Time and space complexity

          

            

              Time complexity
              
O(log(min(a, b))) because each recursive call quickly reduces the remainder.

            

            

              Auxiliary space
              
O(log(min(a, b))) because the recursive calls remain on the call stack.

            

          

        


        

          
DEBUGGING CHECKLIST

          
Common mistakes

          

            

              Missing base case
              
Without if (b == 0), recursive calls may continue incorrectly and exhaust the call stack.

            

            

              Wrong argument order
              
The recursive call must be gcd(b, a % b), not gcd(a, a % b).

            

            

              Using division
              
Euclid's algorithm needs the remainder operator %, not the division operator /.

            

            

              Ignoring input validation
              
For this beginner example, use positive integers so that the recursive flow is easy to understand.

            

          


          
Try it yourself

          

            Practice variation:
            Modify the program so it finds the GCD of three integers by reusing the same recursive function.