Write a recursive function that computes the greatest common divisor of two natural numbers *a* and *b*
using the *fast* version of the Euclidean algorithm.

Interface

C++ | int gcd(int a, int b); |

C | int gcd(int a, int b); |

Java | public static int gcd(int a, int b); |

Python | gcd(a, b) # returns int |

gcd(a: int, b: int) -> int |

Precondition

Neither *a* nor *b* are negative,
and at least one of them is strictly greater than zero.

Observation You only need to submit the required procedure; your main program will be ignored.

Public test cases

**Input/Output**

gcd(66, 12) → 6

gcd(100, 21) → 1

gcd(0, 10) → 10

gcd(100, 21) → 1

gcd(0, 10) → 10

Information

- Author
- Jordi Petit
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C C++ Java Python
- User solutions
- C C++ Java Python