Recursive GCD (Euclid)

Challenge

Implement:

int gcd(int a, int b);

Return the greatest common divisor of a and b (both >= 0) using the recursive Euclidean algorithm.

Input format

a, b >= 0.

Output format

gcd(a,b).

Constraints

gcd(x,0)=x.

Starter code

#include <stddef.h>
/* Greatest common divisor of a and b (a,b >= 0), via the recursive Euclidean algorithm. */
int gcd(int a,int b){ (void)a;(void)b; return 1; }

Common mistakes

Wrong base case; recursing with the wrong pair.

Edge cases to handle

gcd(0,0)=0; order of arguments doesn't matter.

Background lessons

• Recursive number theory