Recursion: Following the Shape of Data

Breaking down big problems into smaller ones is a great way to solve them. Let's see how recursion helps us do this!

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))
    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:

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!


Learn More

Tail Recursion

What is Recursion? Video


  • Clarissa Littler

    Clarissa has worked in mathematics, physics, and computer science research but spends much of her time now trying to make computer science education accessible to a broader audience.

Also In The April 2020 Issue

As students reach the age of 13 the importance of them understanding their rights and privacy online becomes crucial.

The iDTech summer camp recently posted 102 questions. Here are a few with links to the full list.

Being well-read is essential in everything in life, and coding is no exception! Here are some book recommendations to make you a coding master.

The circus is in town, but they're missing one of their colourful balls. Let's make one for them!

Sundials were one of the first ways people kept track of time. But how did they work?

New to physical computing? MircoPython may be perfect or you!

It's project time! In this article we go over how the same processes used in big factories can be used to control a simple LED.

What do bubbles, pancakes, and spaghetti all have in common? They're all great for sorting!

Yee-ha! In the wild wild west of the internet, antivirus software is a must-have partner.

Exploring the concept of RAM and how it helps your MInecraft game run better.

Breaking down big problems into smaller ones is a great way to solve them. Let's see how recursion helps us do this!

How did this pale blue dot that we call Earth first begin? The answer is even more fascinating than imagined.

Have you ever wondered why your computer's mouse is called that? Well it all started with a fellow named Douglas and a block of wood...

How do you power devices at the top of mountains and the bottom of oceans? Let's find out!

Links from the bottom of all the April 2020 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for April 2020.

Interested but not ready to subscribe? Sign-up for our free monthly email newsletter with curated site content and a new issue email announcement that we send every two months.

No, thanks!