GCD Using Recursion

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is GCD Using Recursion. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

In an Informatica data-quality utility, implement a function that computes the greatest common divisor, or GCD, of two integer values. Use the recursive Euclidean algorithm rather than library functions.

The GCD is the largest non-negative integer that divides both inputs without a remainder. Your implementation must support positive and negative integers, and it must return a non-negative result.

Formal Specification

Implement gcd_recursive(a, b):

Input: Two integers a and b.
Output: A non-negative integer representing gcd(a, b).
The inputs will not both be zero.
The recursive rule is gcd(a, b) = gcd(b, a % b) until the second argument is zero.

Constraints

a and b are integers.
-10^18 <= a, b <= 10^18.
a and b are not both zero.
The implementation must use recursion.
The result must be non-negative.

Function Signature

def gcd_recursive(a, b):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output