Help me find mistake in greatest common divisor algorithm in python

Question

So I have written

function gcd(a, b)
  if b <> 0
    gcd (b, a % b)
  else
    return a

print gcd (12, 9)

so it goes:

1. gcd(12, 9)
2. 9 <> 0 means TRUE
3. gcd(9, 12 % 9 = 3)
4. 3 <> 0 means TRUE
5. gcd(3, 9 % 3 = 0)
6. 0 <> 0 means FALSE
7. return a which is 3 but it returns nothing

Could you please help me find my mistake?

Answer 1

I think you need this line:

return gcd (b, a % b)

instead of just:

gcd (b, a % b)

Here's my Python code showing the solution in action:

>>> def gcd(a,b):
...   if b != 0:
...     return gcd(b, a % b)
...   else:
...     return a
...
>>> print gcd(12,9)
3
>>>

This was with Python 2.4.3 on Linux.