Exercises 1

Greatest Common Denominator

Greatest common denominator of two numbers a and b is calculated recursively by:

a if a=b GCD(a,b) = GCD(a-b,b) if a>b GCD(a,b-a) if a<b

Write a function to implement this formula.

First - sketch your function on paper.
Next – implement a program to test it.
Last - make a drawing to show the function-calls involved in calculating GCD(18,8)

See Solution:

function GCDRecusive(a,b){ if(a === b){ return a; }else if(a>b){ return GCDRecusive(a-b,b); }else if(a<b){ return GCDRecusive(a,b-a); } } function GCD(a,b){ var remainder; while (a !== 0) { remainder = b % a; b = a; a = remainder; } return b; }
Result :