Sudoku

Chris Angelico rosuav at gmail.com
Thu Mar 28 23:45:36 CET 2013


On Fri, Mar 29, 2013 at 9:11 AM, Eric Parry <joan4eric at gmail.com> wrote:
> Thank you for that explanation.
> No, I do not understand recursion. It is missing from my Python manual. I would be pleased to receive further explanation from anyone.

If you already know what recursion is, just remember the answer.
Otherwise, find someone who is standing closer to Douglas Hofstadter
than you are; then ask him or her what recursion is.

:)

Recursion is a form of self-referential code. Take this simple, and
rather silly, means of calculating the sum of numbers in a list (like
the sum() function):

# The sum of numbers in an empty list is 0.
# Otherwise it is the first number plus the sum of the rest of the list.
def list_sum(lst):
    if not lst: return 0
    return lst[0] + list_sum(lst[1:])

>>> list_sum([1,2,3,4,5,6])
21

Note how the function calls itself - but not always. That's critical
to recursion - a termination condition. In this case, it's quite
obvious that the list will eventually have nothing left in it, so the
function will terminate. Sometimes it's less obvious. Sometimes a bug
results in infinite recursion... and:

RuntimeError: maximum recursion depth exceeded in comparison

Hope that helps!

ChrisA



More information about the Python-list mailing list