I had a hell of a time understanding recursion back in my salad days, and didn't really come to grasp it fully until I was forced to learn Lisp (Which I highly recommend, by the way). In the hopes of easing the road to this understanding for some future, budding Comp-Sci geek, here's just about the simplest useful recursive function I know, written in Ruby, just about the simplest useful programming language I know.
def factorial(num)
if num == 0
return 1
else
return num * factorial(num - 1)
end
end
Since that won't mean much unless you're already familiar with the ideas behind recursion, we'll step through it using an example.
Say we called this function on the number 4. Anyone who had to learn factorials in school knows that 4! = 4 * 3 * 2 * 1 = 24. What we need to tell our program to do, then, is multiply 4 times 4-1 times (4-1)-1, etc . . . down to 1. Most of this is accomplished through this line:
return num * factorial(num - 1)
What confused me most about recursive functions was figuring out just where in Hell the "work" was getting done. All I saw were a bunch of function calls and a stopping condition! The trick is to pay close attention to those function calls, and look at the arguments they're being passed. In this case, we're calling factorial all over again, but this time we're calling it on 4-1. So what we have on our program stack right now is:
factorial(4)
factorial(3)
It will be called two more times before the stopping condition, which is num equal to 1, is met. Now, when we reach the stopping condition is when the real magic happens. We've got our program stack looking like so:
factorial(4)
factorial(3)
factorial(2)
factorial(1)
and we've reached the point where num is equal to 1. Our program will then return the number 1, just as it's been told to, and unwind the recursion. If you remember our workhorse statement (return num * factorial(num - 1)), you'll recall that it starts with a return. What it's doing is returning the value of whatever num currently is times whatever the previous function returned. It's probably easier to visualize this than explain it:
factorial(4)
^ factorial(3)
| ^ factorial(2)
| | ^ factorial(1)
| | ----returns 1
| ----returns 2 * 1
----returns 3 * 2
returns 4 * 6
So factorial(1), seeing that num is equal to 1, returns 1. Control then passes to the next function on the stack, which is factorial(2). This function returns using the statement return num * factorial(num - 1). Substituting the numbers we know we have into this statement, we get return 2 * 1(1 coming from the previous return statement). The next function up the stack is factorial(3), which receives whatever factorial(2) returned, so it returns 3 * 2, and finally our first function call gets to return, using the result of all those function calls that came before it, returning 4 * 6, which is 24 (Notice that we employed the Distributive Property of multiplication for this. Hooray for maths!)
My hope is that this little example was helpful to someone in coming to understand how to read and create recursive functions. If this by some miracle sparked an interest, I'd recommend learning Lisp to explore recursion more fully, mainly because it's dead-easy to recurse with. Good luck, my friends! Curse, and curse again!