Question

Design a recursive version of the Euclidean algorithm

Answer 1

Here's a recursive Python program that finds the greatest common denominator:

#!/usr/bin/python

import sys

def gcdR( x, y ):
    if( y ):
        return( gcdR( y, x % y ) )
    return x
       

if( __name__ == "__main__" ):
    x = max( int( sys.argv[ 1 ] ), int( sys.argv[ 2 ] ) )
    y = min( int( sys.argv[ 1 ] ), int( sys.argv[ 2 ] ) )

    print gcdR( y, x % y )

    sys.exit( 0 )