First and foremost, do you understand what "recursion" means? If not, it's simply some procedure (method, function, etc) that calls itself. This creates a loop, since we're repeating calls to this one procedure.

The simplest example of a recursive function is (in pseudocode):

function foo() {
    foo()
 }

As you can guess, that's pretty much an infinite loop, because each time we enter the function, we re-enter it, over and over. It's only "infinite" in theory, though. In reality, we have limited memory and every time we enter a function, we need to use some memory (in a part of memory called "the stack"). As a result, this will eventually run out of memory and cause what we call a stack overflow. I won't go into detail on the stack here, but you should take the time to learn it because it's very important for programmers to know.

Anyway, we don't want infinite loops in our code. Thus, we must have some way to stop the recursion. The issue is that each time we enter the function, all the local variables are new (they are "local" to the function call). As a result, we cannot use a local variable to retain data in a recursive call. That is, the follow code will NOT work:

function foo() {
    var loops = 0
    if(loops < 10) {
        loops = loops + 1
        foo()
    }
}

The issue is that every time we enter foo(), we have a new loops variable (which happens to be stored on the stack, if you just looked up what the stack is).

But hope is not lost, there is a way to pass data between the function calls, and that is with parameters and return values. If we pass parameters to a function, we can use these parameters, modify them, and pass them to the next function until they meet some condition.

Writing a recursive algorithm

Let's examine this with an example. Suppose I have a list of numbers and I want to sum them up. That is, I have [1, 2, 3] and I want to sum them to get 6. We'll write a recursive function to solve this.

So, first things first, summing up a number is easy: we must iterate through every number in the list and add it to a running total. Thus, each function call should be consuming an item in the list. When do we stop? When the list is empty (ie, we've processed all the items).

Now, we have one piece of state that we must remember: the remaining (unprocessed) items in the list. That's going to be a parameter. So let's start by writing out the code that will stop on an empty list:

def sum(list):
	if len(list) == 0:
		return 0
	else:
		# TODO

Why do we return zero? Because we're going to be adding each item together (so that [1, 2, 3] will become 1 + 2 + 3) and zero is the identity of addition (anything plus zero equals the original value).

Now, we want to add the value of the current item to the returned value from the next item (which we don't have yet, but the recursive call will return):

def sum(list):
	if len(list) == 0:
		return 0
	else:
		return list[0] + sum(list[1:])

Note that list[0] gets the value at the front of the list (which must exist because we already checked if the list is empty) and list[1:] gets everything after the first item in the list (which will be an empty list if there's only one item in the list).

Examining how that works

That's still probably cryptic, so let's go into how that works. First and foremost, you must understand that sum() is always going to return the sum of the passed in list, somehow. Even before you've finished writing the code, you should know what this function is going to return.

So obviously the first item plus the sum of the remaining items will equal the total sum. That's just basic math. In other words, sum([1, 2, 3]) == 1 + sum([2, 3]). From this, we can also see that 1 + sum([2, 3]) == 1 + 2 + sum([3]) == 1 + 2 + 3 + sum([]) == 1 + 2 + 3 + 0. That's exactly what our algorithm does.

To see that, let's modify the algorithm to print out what it's adding:

def sum(list):
	if len(list) == 0:
		return 0
	else:
		print("%s + sum(%s)" % (list[0], list[1:])) # Only line different
		return list[0] + sum(list[1:])

Executing that results in:

>>> sum([1, 2, 3])
1 + sum([2, 3])
2 + sum([3])
3 + sum([])
6

So if sum([2, 3]) == 2 + sum([3]), then sum([1, 2, 3]) == 1 + 2 + sum([2, 3]). This is mathematical substitution.

Why use recursion

This is actually a very bad place to use recursion. As mentioned, every function call needs a bit of memory. That's not an issue for non-recursive calls because we usually have a lot of memory and the memory used isn't that much. But a recursive function for something that will have to make a lot of calls may end up running out of memory, which is very bad. For example, try running sum() with a very large list.

>>> sum(range(1000))
  File "<stdin>", line 5, in sum
  <REMOVED>
  File "<stdin>", line 5, in sum
RuntimeError: maximum recursion depth exceeded

The stack trace will be extremely long because there's so many nested function calls (which is why I pruned that list here).

This is why we wouldn't want to use recursion in most cases. It's also usually slower because of the extra function call. That's all obviously undesirable.

So why use recursion at all? Because some algorithms are naturally recursive. I won't go into them here, but lookup "merge sort" for an example of an algorithm that is best understood in a recursive manner. There's also data structures that are defined recursively.

For example, Haskell, a language that has a huge hardon for recursion, defines the list as data [] a = [] | a : [a]. What that means is that a list is either an empty list (represented by []) or some item concatenated with a list of the same type (the a represents a type, showing that the type of the concatenated item is the same as the type of the list we concatenated to. The : symbol is simply showing this concatenation and can be thought of as a way to construct lists).

There's also a more efficient solution for recursion, and that's tail recursion, where we pass all the data we need as arguments. This removes the need to do any calculation in our intermediate function calls (ie, we only need the last function call). As a result, we don't need to keep the intermediate functions in the stack. Python does NOT have tail recursion, so I cannot show it to you in Python, but here's a Haskell example:

mySum runningSum [] = runningSum
mySum runningSum (x:xs) = mySum (runningSum + x) xs

The (x:xs) just extracts the head from the tail and is called "pattern matching". As a result, x is assigned the value at the front of the list and xs is the remaining list. So x is equivalent to list[0] in our Python code and xs is equivalent to list[1:] in our Python code.

And we can now demonstrate that this works with very large lists (unlike our Python code):

λ mySum 0 [1 .. 100000]
5000050000