logo CodeStepByStep logo

Main Page → Exercises → C++ → Solve an Exercise

gcd

Language/Type: C++ recursion return

Write a recursive function named gcd that accepts two integer parameters a and b and returns their greatest common divisor. The greatest common divisor (often abbreviated as "GCD") of two nonnegative integers is the largest integer that divides evenly into both. For example, the call of gcd(36, 24) should return 12.

In the third century BCE, the Greek mathematician Euclid discovered that the greatest common divisor of a and b can be computed as follows:

  • If a is evenly divisible by b, then b is the greatest common divisor.
  • Otherwise, the greatest common divisor of a and b is always equal to the greatest common divisor of b and the remainder of a divided by b.

Use Euclid's insight in writing your recursive function.

Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.