This section has only one real rule: a function can call itself. Each time, you
get a fresh copy and a fresh set of local variables. That’s the whole rule.
As you might guess, the real skill is being able to use it to do something
useful.
The first part of this chapter is showing the mechanical rules for recursion – no actually useful examples yet. Then next part will be real, but fakey uses of recursion - doing things recursively that we can already do better without it.
Then the last part will be about real problems where recursion is the best
way.
Recursion is a tough topic. You have to just “get” it, and even after that it’s a tricky thing to do right. But unlike some other hard topics, knowing just a little is useful.
What will happen is: some problem you’re trying to solve will naturally break into parts. You’ll notice these parts are the same as the original problem, just smaller. And those break into subparts that are the same way, and so on. That’s a naturally recursive problem, which means you need recursion to solve it (hopefully by the end of this chapter at least that will make sense.)
Just being able to recognize a recursive problem is a real time-saver, which isn’t
too hard once you’ve seen a few examples.
Another funny thing about recursion: you know how with most tricks – like functions, loops and lists – you should have been using them all along? Recursion isn’t like that at all. It’s pretty much useless except for those few special problems that can’t be solved any other way.
A function is allowed to call itself. Just like calling anything else, it waits for the call to end, then continues. The function crashMe below is useless, never prints anything and will crash the computer, but it is legal:
When this calls function crashMe(), the computer starts running a second fresh copy. The first crashMe call is waiting, and the second copy is running. The second copy calls the third copy and waits, and so on.
This makes an infinite number of copies, never getting to line 2 of any of them. A
fun fact – each copy takes a little bit of space. So instead of running forever like
an infinite loop, it runs out of memory and crashes the entire Unity editor
(same as an infinite loop, be sure to save before testing if you changed the
Scene.)
Having a chain of crashMe’s, all waiting for the next one to finish, isn’t the
problem. Never stopping is the problem. We can use tricks to make recursion end,
just like we use tricks to make loops end.
This next recursive function is still pretty useless, but it will run without crashing:
It works because of the “make a copy of” rule. Each time we call A, we get a new copy of it with a new local n.
Saying this in a different way: the idea I gave you before about local variables was
oversimplified. I made it seem like you could premake one local n, which A used
whenever it was called. The real trick is we really make a fresh local n for each
call.
Suppose someone calls A(5). It calls A(4), which calls A(3) …down to A(0), which stops because of the if. Here’s what the call stack looks like after that:
Five copies of A are waiting, with their own local n’s. The last copy with n=0 is running. It prints 0 and pops back to A(1). That local n is 1. We print that, pop back and print 2 and so on.
A neat thing, pretend you’re the first A(5). All you do is call A(4), wait, then
print 5. All that growing and shrinking the call stack is handled by the computer. It
seems like this is different because the function you’re waiting for is you, but it’s
not.
The whole thing prints 0 1 2 3 4 5, on different lines. To be clear: this isn’t a good
use of recursion (but it’s pretty cool that it works at all.)
If you think back to the old “function calling some other function” examples, it was nice to print some variables just before and just after the call. This standard recursion example does that. We can watch it “go down” and then come back:
Not even thinking about recursion, we can see B(3) will print begin: 3 first, then some middle stuff, then DONE: 3 as the last thing. The entire output is:
It’s sort of the same logic as when A calls B calls C. The middle part is what B(2) does. And the middle of that is what B(1) does. But even so, yikes!
A recursive function starts with a recursive idea. You have something you can
solve by doing a little bit of work to make it the same problem, but smaller.
Then you run a copy of yourself solve the smaller version, which repeats the
process.
Here’s a recursive idea to compute powers of 2: to get 2n, find the next lower one and double it. For example, 24 is two times 23. It’s recursive since 23 is the same problem, but smaller. Another copy of ourself can be used to solve it:
Let’s forget about how we can already do this with a loop. Do you see how beautiful that last line is? return 2*powTwo(p-1). It says “call a function to find the next lower power of two, double it, and I’m done.”
If powTwo(3) computes 8, then powTwo(4) will compute 16.
Here’s a picture of the largest stack frame if we call twoPow(4). Four functions waiting for the fifth to finish:
The fun part is when they start returning things. Each one gets the “one lower” answer, doubles it, and returns that. As the functions pop back, the return values look like the second line:
I think of it as a bunch of guys in a row. Each guy asks the one to the right, then
waits. Eventually, they hear the answer, double it, and tell that to the guy who asked
them.
You may have realized the “how do I stop” problem is similar to the one we had with loops. So far, we’ve been counting down to 0, but, like loops, recursion can have all sorts of plans for when to stop.
In this next one I want to pad a string up to a certain length by adding dashes around it. For example "cow" padded to 8 would be "--cow---". My recursive plan is this: add a dash on each side and have someone else finish it. And, of course, check if you only need one dash.
The key is how lazy it is. Adding a dash on each end is like a single step of work, and the result is a “more done” version of the same problem. We can hand it off to another version of ourself. The code:
Some notes about this:
You might notice one difference between recursion and loops: when a loop ends, it just ends. Recursion usually ends with an answer. It ends by saying “hey - this input is so easy I can just do it.” We call that the basis step.
In the power-of-2 functions, the basis step is p=0. In this one, there are two basis
steps: big enough, and only needs one more.
This next one is another oddball: finding the largest thing in part of a list, using recursion. The plan is to grab the first item, use recursion to find the largest thing in the rest, and compare:
Like before, this isn’t a place where we’d normally use recursion, but it’s still neat
to see how lazy it is. Each copy only compares 2 numbers.
This shows another funny thing about recursion. This only works since it has start as an input. We need it so we can add 1 when we call ourself. This is pretty common. It’s also common to add a non-recursive front-end:
For recursive functions we often call that a driver. Sometimes it has to set up a
lot of variables. And then it often has to decode the answer from the recursive part
into what we really wanted. So we thought a fancy name like Driver sounded
better.
This last example uses a few tricks and also feels very recursive-y. Suppose we have a sorted list and want to check for a number. Since it’s sorted, we can look at the middle number, pick the correct half, and search there. Saying it recursively: to find a number in a list, find which half it has to be in, and search that half.
To cut the list in half, we’ll have to use the trick where the recursive part takes start and end, and a fake front-end driver fills them in:
Here’s the recursive code, with extra prints:
Getting the math correct for the halves is tricky – there are lots of places to have an off-by-one. But those are details. Instead look how beautiful the recursive calls are: bSearch(A, start, mid, num) checks the first half and bSearch(A, mid+1, end, num) checks the second half.
A new thing is that previously we made exactly the same recursive call every
time. Now we choose which one. But the important thing is we’re always getting
shorter, and closer to being done.
Some notes: 1) This only works if the list is sorted, 2) there’s already a built-in
BinarySearch in the List class, 3) for real a loop is better: each time would move
start or end and it stops when they touch, 4) it’s called Binary Search since it cuts
into 2 halves and binary means 2.
There’s one more funny thing about this. Suppose we cut it in half 6 times to get down to the smallest list. That means a chain of 6 functions is waiting for us. We know the answer but there’s no way to directly send it back.
We return true or false, and everyone else just sends the same answer up the chain. That’s what return bSearch(A, mid+1, end, num) does – whatever she said, that’s my answer to.
It seems wasteful, but there’s no other good way.
The computer science term for parents with children, with yet more children, is a tree. A tree is a recursive data structure, which means only recursion is good at navigating one.
Folders with files and more folders inside is a tree. In Unity (or any 3D
environment) trees are commonly used to glue objects together.
Suppose we make three long, thin cubes for fingers, positioned against a flat square for a hand. Moving the hand would leave the fingers behind. To glue them to it, drag them in to make them children. You get this picture:
Now moving or rotating the hand drags the fingers with it. It’s a feature. You
can move or tilt any of the fingers, and it will follow the hand using that
new, adjusted position. For real, animated 3D models have one “skin” and
lots of imaginary bones organized in a tree. So you see this sort of thing a
lot.
A more realistic tree might start at the body, with 2 hands a head and a tail, which also have several parts:
This is showing how trees are a recursive data structures. body is a tree, but hand1 is also a tree. head is a very small tree. The definition of a tree is a parent, with 0 or more children, which are also trees. The definition loops around back to itself.
It sounds like cheating, but it works pretty well: tailA has tailB inside of it.
What are the rules for tailB? Well, it is also a tree, so the rules say it has 0 or more
child trees in it.
Before using recursion, we need Unity’s tree commands. They work off of the Transform. transform.childCount is an int, which can be 0. transform.GetChild(n) gets one child, using the usual 0-based index (three children go from 0-2).
A sample non-recursive function to print someone’s name and all of their immediate children:
The problem is each child could have more children, or not. Some children could have lots of levels of grand-grand-grand-children.
Here’s the super-cool part: each child, by the definition, is another tree. To print everything in a tree, we call the tree-print function! The recursive function:
This is so cool. You don’t even print the names of your own kids. They’re fully trees on their own, so send them to another treePrint.
Some notes:
A recursive function making one call each time is just a bad way to write a loop (but is still a good way to practice.)
And now body can finally call hand2.
But that’s not a new rule. We already knew that function A can call B, do more stuff, and call B again, since it always resumes from where it left off. But yikes does recursion make it seem complicated.
Printing in order of depth (all children, then all grand-children …) makes as much sense, but there’s no easy tweak to do it. Recursive functions can be delicate – they work the way they work
To show those last two points, this will take any tree made of simple objects and turn them all a color. It’s a copy of the same code with “change color” where printing was:
This next example is to show how recursion can be deceptively hard. Suppose instead my plan was to color each child as I saw it, then make a recursive call only if it had children. That “feels” better and seems like it would run faster, but it has a bug:
The bug is it won’t color the main parent (body, in my example.) We could add
that, but then it would color everything twice. It’s not an error in this case, but for
some things it would be.
A classic tree function is counting everything in the entire tree. It’s dastardly how something this short actually works (I’m also using a shortcut for going through every child):
It doesn’t even add tt.childCount! It hits every item, in the usual way, and counts them all as 1.
You can test it recursively! On a childless item it returns 1. If we have four
normal children, the loop runs 4 times, adding +1 each time, which makes five.
Suppose we have two of those things in one parent. The answer is 1 + 5 (call on 1st
child) + 5 (call on 2nd child).
That’s the way to figure out tricky recursive stuff. Test it on a small thing. When you try it on something larger, all of the recursive calls will be on something you just tested.
Finding all of the connected spaces in a 2D grid turns out to be another recursive problem. The solution works out to: mark this space and find all of the free spaces touching it. For all of those spaces, repeat.
That’s often called a Flood Fill. Various problems can be solved with it:
checking whether every space on a map is connected, or checking whether a
fence keeps in a cow (do a flood fill from the cow. Check it can’t reach the
road).
We’ll run this in Unity, so we can see the results in color. That means we need a bunch of boring grid code. You can skip straight to the recursive part. The grid details are mostly obvious.
Boring grid set-up: each square is either a wall or open. Open spaces have a Mark, used to indicate reachable spaces. We’ll color walls blue, open areas white, and marks green.
Here’s a simple class to handle one square. G will be our permanent link to the real square, which we’ll make later:
The string-picture trick is a cheap way to describe a grid. This one has some interesting differently-shaped areas. The o’s stand for walls:
Then here’s the code to make it all on the screen:
Nothing special or new there. As usual, lots of trial and error and off-end errors to
get it to line up.
The flood fill is another way-too-short-looking recursive function. Remember the plan is: mark this space; find all of the free spaces touching it and repeat:
If you run this, and give xStart and yStart various values, you should see the different areas turn green. A fun thing is maybe you’re not sure where (0,0) is. Run it with (1,1) and see which part turns green.
Some notes:
We didn’t have to make marks for trees since there’s only one way to get to each thing.
It might be nicer if the 4 calls at the bottom checked for being open before making the call. But it’s so cool that only checking the space we’re in right now also works.
The starting square will call “walk left” and might wait a very long time before it gets to walking right.
Finding a path between one space and another is a variant of flood fill. The difference
is you stop if you land on the destination, and need some way to remember the
path.
The secret to saving the path is remembering how the call stack works. If we’re sitting on a space 6 moves from the start, we’re at the end of a chain of 6 functions which each took one step.
The plan to save the path is to start with a global empty list. Whenever we take a step (including the start space) we’ll add that (x,y) to the end of the list. Whenever give up on a space, we’ll take it off. The saved list of steps will always be exactly the steps in the function chain we’re on now.
Here’s the code, with set-up:
Running this, with hand-entered start and end’s, will make a green path
between them. But it’s still not smart – it still follows the same winding
path in an open area. But it works great if you add walls to make it more
mazey.
A fun thing to do is watch this work in slow motion. This next thing is the same maze walk, except it always shows the current path. It will always show a path of green squares, matching the current chain of function calls:
The Unity trick using an IEnumerator to slow it down is sneaky, and this doesn’t save the path anymore. But it’s one of the nicer ways to see recursion working. If you run it in a more open area, you’ll even see how each call tries to follow the same pattern.
It’s very, very easy to get an infinite recursion by mistake.
This tree function accidentally make the recursive call on itself, instead of on a child, so spins forever:
In this one, the driver accidentally calls itself, instead of the recursive function: