recursion.rb

def gcd_recursive(u, v)
return u|v if u==0 or v==0

if u.even?
  if v.even?
    return gcd(u>>1, v>>1)<<1
  else
    return gcd(u>>1, v) if v.odd?
  end
elsif u.odd? and v.even?
  return gcd(u, v>>1)
else
  if u < v
    u, v = v, u
  end
  return gcd((u-v)>>1, v)
end
end

def gcd(u, v)
  return u|v if u==0 or v==0
  shift=0
  while ((u|v)&1)==0 do
    u=u >> 1;
    v=v >> 1;
    shift += 1
  end
  while ((u&1) == 0) do 
    u=u >> 1
  end
  begin
    while ((v & 1) == 0) do
      v=v >> 1
    end

    if u < v
      v -= u
    else
      diff = u - v
      u = v
      v = diff
    end
  end while v != 0
  u<<shift
end