Recursion is one of the foundational tricks for solving problems, on a computer or otherwise. Even if you’ve never heard the word before you may have seen the idea!
Basically, recursion is when you break a problem into smaller parts you can solve individually in order to solve the bigger problem. Recursion is also when you have something that references itself, like the joke Google pulls if you search for the word “recursion”
These two definitions are really the same thing, which we’re going to demonstrate with a little math example: the factorial function.
If you haven’t seen the factorial before it’s kind of the “Hello World” of recursion. We write the factorial of a number like 5! or 10! and what the factorial does is this
5! = 5*4*3*2*1
10! = 10*9*8*7*6*5*4*3*2*1
The value of all the elements of 5! multiplied together is 120 while the value of 10! is 3,628,800.
In terms of a generic number n we could define factorials as
n! = n*(n-1)!
Oh, that’s a nice and short definition isn’t it? So what about making the factorial in, say, Python? If you don’t want to use recursion you’re going to need to write a factorial function like
def fact(n):
total = 1
for i in range(n):
total = total*(n-i)
return total
# this should print 120
print("5! is %d" % (fact(5)))
and this isn’t wrong but it’s not super obvious why it’s right.
Let’s use recursion instead of a for-loop:
def fact(n):
if n > 1:
return n*(fact(n-1))
else:
return 1
print("5! is %d" % (fact(5)))
Neat! This matches closer to how you’d define the factorial in math and, in my opinion, is a little bit easier to read and tell what’s happening.
The convenience of using recursion shows up really quickly once we start talking about more complicated shapes of problems. Factorials have a really simple shape: counting down to 1 from a start number.
Here’s another example from your math classes! Consider this expression:
3+2*(5+4)
What kind of shape does it have? It’s not just a simple shape like the factorial, because if you evaluated everything in a line you’d get the wrong answer: 3+2*(5+4)= 5*(5+4) = 25+4 = 29. No, this has a shape like a tree because of the order of operations! Order of operations is a set of calculation rules people agree to follow. For example, multiplication is processed before addition. 3 + 2 * 5 + 4 is processed as 3 + (2 * 5) + 4.
If you go down the tree and calculate the result of the sub-trees before moving up you’ll be able to respect the order of operations. This is a recursive solution to the problem. If you wanted to write a program that acts as a calculator you’ll have to write a function that does exactly that: descending the tree and calculating all the sub-parts before combining them together!
Also, here’s something neat: if you ever want to implement a programming language it’s basically the same thing: a recursive function that goes up and down the shapes of trees. It’ll be a bit more complicated than just adding and multiplying, but the basic principle is the same!
So recursion is a way of writing code that is sensitive to the shape of the data you’re working with, for solving complex problems by breaking them into simpler parts. There’s even more to it, though, like how to make recursive functions run really efficiently—more efficiently than even loops—with things like tail recursion. If you want to know more or see more examples check out the links in the rest of the magazine and the article on Snap! in this issue!