Recursion --------- A Python function may use itself in its definition (or a group of Python functions may all use one another in their definitions). This seems circular to some people, and there is a circularity about it. But this doesn't mean that it's not useful. Here's a case where this recursion is not useful: def useless(x): return useless(x) This function just calls itself, no matter what, and returns its own value, but to find its value, it has to find its value, and to do that, it has to find its value. If you use this function, it will get stuck in an infinite loop and never return (although in practice I expect that you'd get an error after a little while). Here is a pair of similarly useless functions: def foo(x): return bar(x) def bar(y): return foo(y) As you can probably see, these functions also become mired in an infinite loop. This is kind of like doing while 1: hello = 2 which sets hello equal to 2 an infinite number of times in a row. Oops. (There _is_ a perfectly legitimate use for "while 1:", but that's not it.) On the other hand, in cases where something _is_ naturally defined recursively or inductively, recursion can be helpful. The most famous and classic example is the factorial function in mathematics. If you have 5 people (say, the 5 people in our class) and 5 seats, how many ways can you arrange the people in the seats (given that each seat is used and only one person can fit on each seat)? If you look at it from the point of view of the seats, you have five choices about how to fill the first seat. Once you've filled that seat, you'll always have four choices for the second seat (no matter whom you put in the first seat, there are four people remaining), and these choices are independent, so that there are 5*4=20 ways of filling the first two seats. For each of those choices, there are then three ways of filling the third seat (so 5*4*3=60 ways of filling the first three seats), and then two ways of filling the fourth seat (so 5*4*3*2=120 ways of filling the first four seats), and then only one person is left, so there is only one way of filling the seats. This is an example of the factorial function, which is the result of multiplying together all the integers from 1 to n. (The factorial of n is usually written n! by mathematicians.) So for example 5!=1*2*3*4*5 or 5*4*3*2*1 and 10!=1*2*3*4*5*6*7*8*9*10 Notice that n! is always (n-1)! times n. This makes a recursive explanation of a factorial function very simple: def factorial(n): return n*factorial(n-1) Oops, what's wrong with this definition? Well, it's an infinite loop. It will go on forever. Is it _really_ true that "n! is always (n-1)! times n"? Not exactly. We didn't define or explain what the factorial of 0 is, or of any negative number. Is it true that (1)! is (1-1)!*1, or (0)! is (0-1)!*1? Mathematicians choose to define 0! to be 1 (it makes the accounting easier, so to speak). This means that the rule "n! is always (n-1)! times n" is still true when n is 1 (because 1! is 1 which is the same as (1-1)!*1). On the other hand, factorial is not defined for negative numbers; we can say that the factorial of a negative number is meaningless. This means that the rule _isn't_ true when n equals 0; that's a special, unique case. So the rule for calculating factorial(0) is _different_ from the rule for calculating factorial(anything else). Does that mean that we have to write a whole new function? No, we can just make the definition of factorial a little bit more subtle by adding an if statement: def factorial(n): if n == 0: return 1 else; return n*factorial(n-1) And this works -- you'll see that factorial(5) gives 120, as it should. You can also try map(factorial, range(1, 10)) to see how quickly the factorial function grows. There's a common saying in programming that recursion has to have a "base case" (to prevent an infinite loop). Some people interpret this to mean that there must be a number which gets smaller all the time and a different rule to handle the situation when that number reaches the "bottom". This view of recursion is somewhat too narrow; if you think of recursion as a loop, or as a trip through an enchanted forest, the point is simply that, if you don't want to stay there forever, there must be some way out, and you must be able to reach the way out. We don't necessarily have to say what the way out _is_. It doesn't necessarily have to be a "number always getting smaller"; maybe a fairy shows up and waves a magic wand, or maybe you find a door in the side of a stone, or climb a tree and are carried away by an eagle, or fall through a trap door and end up somewhere else entirely. The point is just that there should be a way out. And, if you want to get out, you should come to it eventually. It's true that the most common recursion examples do use a variable which gets constantly smaller (or constantly larger), or a sequence type whose _size_ gets constantly smaller. But this form is not an absolute requirement. There are good reasons to write recursive code where the objects you're dealing with may well grow _and_ shrink, perhaps many times, before you've reached the end. (One common example is a queue technique, where you have a sort of to-do list. You won't be done until the to-do list is empty, but you may well add and remove things many times before you're done. Furthermore, the act of doing one thing on the to-do list may well involve adding other sub-tasks to the end of the list, so that the list actually appears to get longer, much as your room may temporarily become messier while you're re-organizing it.) There are even, in principle, sometimes good reasons in computer science to write recursive functions which don't necessarily terminate at all. You just wouldn't want to call them in an actual program with input which makes them loop forever, or you'll be waiting a long time for the results. With a little more work, we can also use recursion to find out what the 120 seating arrangements themselves are: def fill_seats(people): # Return a list of ways to fill len(people) seats with the people # named in the sequence people. if len(people) == 0: return [] else: possible = [] for i in range(len(people)): this_person = people[i] everyone_else = people[:i] + people[i+1:] for seating_arrangement in fill_seats(everyone_else): possible = possible + [[this_person] + seating_arrangement] return possible our_class = ["Biella", "Gwen", "Katie", "Seth", "Will"] for arrangement in fill_seats(our_class): print arrangement print len(fill_seats(our_class)), "total possible arrangements." This code is actually a complete solution to the problem of generating all the permutations of a list. A list's permutations are also known as its derangements, which is not meant to suggest that our class is deranged. Can you re-write this to give derangements of strings instead of lists? It should only require two tiny changes. Here are some recursive defintions of the "len", "range", and "map" functions with which you're familiar. They take advantage of the rules about when something is considered "true" (if it's non-zero or non-empty). def rlen(seq): if seq: return 1 + rlen(seq[1:]) else: return 0 def rrange(x): if x: return rrange(x-1)+[x] else: return [] def rmap(f, seq): if seq: return [f(seq[0])] + rmap(f, seq[1:]) else: return [] # This one reads a list of numbers typed by the user, but stops # when 0 is entered. You need to run rloop([]) to use it. def rloop(so_far): x = int(raw_input()) if x: return rloop(so_far + [x]) else: return so_far # This is a nicer version, which doesn't take an argument: def rloop(): x = int(raw_input()) if x: return [x]+rloop() else: return [] These sorts of recursion are the normal method of doing loops in Scheme and LISP. If they appeal to you, you might want to try to learn Scheme! Python has the "for" and "while" statements, so you don't usually need to use recursion for loops. But sometimes it may seem natural. One of my favorite recursive functions I've written recently was one to tell you the factors of a number. Can you think of how to do that? Here's a hint to get you started: def divisible_by(n, divisor): return not (n%divisor)