Помогите мне найти ошибку в алгоритме наибольшего общего делителя в Python

Question

Итак, я написал

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

print gcd (12, 9)

вот так:

1. жк (12, 9)
2. 9 <> 0 означает ИСТИНА
3. gcd (9, 12% 9 = 3)
4. 3 <> 0 означает ИСТИНА
5. gcd (3, 9% 3 = 0)
6. 0 <> 0 означает ЛОЖЬ
7. возвращает a, равное 3, но ничего не возвращает

Не могли бы вы помочь мне найти мою ошибку?

Answer 1

Я думаю, вам нужна эта строка:

return gcd (b, a % b)

вместо просто:

gcd (b, a % b)

Вот мой код Python, показывающий решение в действии:

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

Это было с Python 2.4.3 в Linux.