**Reading**: *None*

**Assignment Due**: Friday, November 9, 2012 at 5:00 PM

- How to solve problem #2 of Homework #2
- Recursion
*n*factorial [nfact.py]- Fibonacci numbers [rfib .py]
- Sum of digits [sumdigits.py]

- Speed: compare iterative and recursive Fibonacci programs [timefibs.py]

**Problem #2, Homework #2**

Write a function `gcd(m, n)` that calculates the greatest common divisor of `m` and `n`. The greatest divisor of *m* and *n* is the largest *positive* integer *k* that evenly divides *m* and *n* (that is, divides both of them giving a remainder of 0). Use Euclid’s algorithm to calculate this. Here is one very succinct way to describe the algorithm (as usual in Python, *m* % *n* is the remainder of *m* when divided by *n*):

When *n* is 0, the value *m* is the greatest common divisor of *m* and *n*. Then write a program that calls your function repeatedly, until the user enters 0 for *n*. Here is an example run of such a program. What the user types is in ` italics` and the symbol “↵” means to type a return or enter. Please do not try to make the input in italics and show the return symbol in your output, of course!

First number (0 to stop):113↵ Second number:293↵ The greatest common divisor of 293 and 113 is 1 First number (0 to stop):14↵ Second number:18↵ The greatest common divisor of 18 and 14 is 2 First number (0 to stop):-30↵ Second number:-66↵ The greatest common divisor of -66 and -30 is 6 First number (0 to stop):7↵ Second number:0↵ The greatest common divisor of 0 and 7 is 7 First number (0 to stop):0↵

Please call your program “gcd.py”.

A PDF version is available here.

ECS 10, Basic Concepts of Computing Fall Quarter 2012 |