Euclidean algorithm (GCD) with multiple numbers?

Question

So I'm writing a program in Python to get the GCD of any amount of numbers.

def GCD(numbers):      if numbers[-1] == 0:         return numbers[0]       # i'm stuck here, this is wrong     for i in range(len(numbers)-1):         print GCD([numbers[i+1], numbers[i] % numbers[i+1]])   print GCD(30, 40, 36) 

The function takes a list of numbers. This should print 2. However, I don't understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

updated, still not working:

def GCD(numbers):      if numbers[-1] == 0:         return numbers[0]      gcd = 0      for i in range(len(numbers)):         gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])         gcdtemp = GCD([gcd, numbers[i+2]])         gcd = gcdtemp      return gcd 

---

Ok, solved it

def GCD(a, b):      if b == 0:         return a     else:         return GCD(b, a % b) 

and then use reduce, like

reduce(GCD, (30, 40, 36)) 

Answer 1

Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python's reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:

if len(numbers) > 2:     return reduce(lambda x,y: GCD([x,y]), numbers) 

Reduce applies the given function to each element in the list, so that something like

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d]) 

is the same as doing

gcd = GCD(a,b) gcd = GCD(gcd,c) gcd = GCD(gcd,d) 

Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.