Recursion is powerful and takes a bit of getting used to. It’s like splitting your thoughts into multiple tasks that are all similar and waiting on the next thought to complete. I know, it sounds complicated. This episode should help you understand this topic that scares and confuses a lot of people.
For the factorial example given in the episode, imagine you have a method declared like this:
int fact (int value);
This method returns an integer and takes an integer. In order to calculate a factorial, it called itself and passes one less than the value it was called with. It keeps doing this until it eventually calls itself with a value of 1. That’s its base case and is a value that it checks for each time. When it sees that it was called with a value of 1, then it returns 1. And each time it returns in the non-base cases, then it takes the return value and multiplies that with the current value and returns that result.
So if this method is called with 4 initially, then the process looks like this:
Some outside code calls fact(4)
Is 4 equal to 1? No. Call fact(3)
Is 3 equal to 1? No. Call fact(2)
Is 2 equal to 1? No. Call fact(1)
Is 1 equal to 1? Yes. Return 1.
The fact(2) instance receives the return value of 1, multiplies it with 2 and returns 2.
The fact(3) instance receives the return value of 2, multiplies it with 3 and returns 6.
The fact(4) instance receives the return value of 6, multiplies it with 4 and returns 24.
The outside code receives the value 24 and has its answer.
You can also use recursion to process binary trees. In this case, instead of just calling a recursive method straight to a single base case, the method can call into its left child and then into its right child. There are now multiple base cases. Each node in the binary tree without children becomes a base case.
Listen to the full episode for more about recursion, or you can also read the full transcript below.
Transcript
Imagine a new law that creates a government office with a lot of secret documents and a lot of power. How do you make sure that office doesn’t abuse it’s power? The answer is obvious, right? Appoint a new government office to watch over the first office. Now these are smart officials who created this new law and had the foresight to recognize how easy this would be to spiral completely out of control so they designed the law with an end to this madness in sight.
You see, they had the brilliant idea to make the second office just a little less secretive and with just a little less power. They thought they were done and about to take a well deserved vacation when one outspoken official asked, “But, who’s going to watch the watcher?”
They debated this for a while and being very creative individuals, decided to just appoint a third office to watch the second. The third would be just a little less secretive and with just a little less power. The thought was that by reducing the secret documents and the power, then there would be less incentive for these watchers to commit a crime. So they could be trusted to perform their duties.
They were about to call for that vacation, when the outspoken official stood up and said, “I don’t know. I think we need to continue this process until there are no more secret documents involved and no more power at all. Only then can we trust the last office to do its job.”
This caused an uproar with comments like, “How would we pay for all these offices,” and “If there’s no power then how can the final office do anything?”
They went on like this for quite a while until they realized that they couldn’t continue creating an infinite number of offices of the same power and they couldn’t have just a few offices that watched each other either. Both of these scenarios would lead to infinite coverups and fraud. They had to find a very small and trustworthy source who could be relied on to always do a simple job without failing. Only then could they build on that base and start creating ever more secretive and powerful offices until the original office could be created.
The officials never did find their simple base and in the end the whole law was scrapped and they went home to their vacations feeling good about all the hard work that was done debating and throwing out the law to create the secretive office.
If only there had been a computer programmer in this group of officials, the whole exercise would have been recognized right away as a recursive procedure.
In order to consider recursion, you must have a base case. Something that can be solved trivially without needing to continue the pattern of recursion. This is the last step in recursion and is what stops the process from going deeper.
You just need to create a method that tests for the base case every time because you don’t know ahead of time how many steps it’ll take to get there.
If you’re not yet at the base, then you do some work to help simplify or make the problem smaller and then call the same method. Yes, the method calls itself. But the key is that each time the method calls itself, it should do so in such a way that will bring the base case closer.
Most recursive methods will test for the base case right away and if it exists, then either perform the work right there or call some other method that’s not going to continue the recursion to do the work. When the result of the base case is ready, then this result is returned to the caller.
The first caller that will get the base case result will be the method that called itself right before the base case. This instance of the method call will take the result from the base case and incorporate it into the work it already did. Or maybe it uses the result right then. That’s not really important. The important part is that this method instance now has done enough work to eventually return too. You can think of this as if it has now become the new base case but with a slightly more elaborate result.
Each of these returns will trickle back up the call chain until finally the original method call can put everything together.
A really common example of recursion is how you might use it to calculate factorials. A factorial of a number is just that number multiplied by one value less and then by one value less again and so on until you get to 1. So 4 factorial is equal to 4 times 3 times 2 times 1.
You could have a recursive method that calculates factorials by declaring a method, let’s call it fact which returns an integer and takes an integer. Some code will get the process started by calling fact and passing 4.
The first thing fact should do is check if the number passed to it is 1 or not. Actually, it should probably make sure the number is greater than or equal to one and throw an error if some code tries passing invalid parameters. Assuming the input is valid and not 1, then it just call itself with a value that’s one less than what it was called with. Eventually, the call chain will call fact with a value of 1. We know this because it keeps getting smaller each time. What we don’t know is how many times it takes to get here. But that’s okay. Eventually we get to one and then instead of calling fact again, we’ve reached the base case and just return 1. The caller of 1 was either the original code that asked for the factorial or it must have been the fact method that was called with the value 2. If we reached the original caller, then that code now has the answer it was looking for. If not, then we keep returning. And each time we return, we multiply the return value with the value that’s one greater.
We end up starting at some number, say 4, and that calls fact with 3, that calls fact with 2, and that calls fact with 1. Then that returns and multiplies 1 with 2 and returns 2. That multiplies 2 with 3 and returns 6. That multiplies 6 with 4 and returns 24. And that returns to the outside code that called fact in the first place.
Now you don’t need to always return values from your methods to be able to use recursion. I’ll explain this right after this message from our sponsor.
( Message from Sponsor )
The previous recursion example calculated a factorial by diving ever deeper and into smaller numbers until it reached 1. Then it started calculating factorials as it returned the ever increasing result of the multiplications back up until it reached the original number. This process used return values and made a straight dive all the way down and then back up again.
That’s recursion because it called itself repeatedly with a value that brought it closer to the base case and then stopped calling itself and started returning once it detected the base case.
But what if we’re not interested in calculating anything? Maybe your code just needs to perform some work on a series of items until some final condition is detected? You could use recursion for that as well. You would still call the same method itself with values that brought it closer to the base case and then either did the work you wanted on the way down or you could do the work on the way up.
I look at it this way. Do you buy Girl Scout cookies on your way into the grocery store or on your way out? Either way, you’re going to buy those cookies.
This is still a straight path to the base case and then back out again.
Is it possible to have multiple base cases? Sure, you could test for 1 in the fact example and return one and maybe you could try to optimize this because you know already what the fact of 2 is and could treat that as another base case and return 2. But this is not what I’m talking about. Creating multiple base cases like this just complicates your code with usually little gain. I say usually because who knows, maybe you really do have a scenario where this would help.
What I’m talking about with multiple base cases is when you don’t have a straight line all the way to the base case and then back. Episode 41 describes binary trees. You can use recursion very well on binary trees. In this case, each node without any children becomes its own base case.
Let’s say we have a binary tree that contains a bunch of items with a color property and we want to go through the entire tree and change each color to red. We can use recursion for this. Let’s create a recursive method called paint that returns void and takes a binary tree node as its parameter.
Just start by calling paint with the root node and make that node red. Then the paint method checks if there’s a left node and if so calls itself and passes the left node. This is recursion because it is calling itself and each time, it gets closer to some node without a left node. This process will continue all the way down the left side of the tree painting each node red. Eventually, it’ll reach a node that has no left child and return.
And here’s the interesting part. Instead of returning all the way back to the start like we did when calculating the factorial, this time, the recursive paint method will check if there’s a right node. If so, then it’ll call itself and pass that right node.
Now this doesn’t suddenly switch everything into some new right child processing mode. the same paint method is being called and what does it do first? It paints itself red and then starts looking for a left node again.
You see, each time, the process will perform work on the current node, then move to the left, then move to the right, and only then will it return.
This is called a pre-order traversal because the current node is processed first before the left or right nodes.
But you don’t have to follow this order. You can also choose to start with the left node, then process the current node, and then dive into the right node. If you do things in this order, then it’s called an in-order traversal because you’re doing things in a sorted order. Remember a binary tree has smaller or equal items to the left and greater or equal items to the right. When you process left, then current, and then right, you’re doing things in-order.
And finally, you could decide to go left first, then go right, and then do whatever yo need for the current node. That would be a post-order traversal.
Regardless of what order you do things in, the fact that you have multiple paths through a tree and multiple nodes without children means that the recursive method no longer has a straight line to just a single base case.