Understanding Recursion: Part 4/4

In the previous posts, we understood the basics of recursion, we discussed what happens when a recursive call is made and we saw some recursive code. But all that was from a programmer’s perspective. We looked at how we would see it. In this post, we will talk about about recursion from a machine’s perspective. We will see what happens inside when a recursive call is made. Don’t worry if you are not a hardcore coder, we will not be using too much jargon here. You will still be able to understand what we are about to discuss.  

How Recursion Really Works

When you write a recursive function, the function clones itself. In the process, it makes new copies of the code along with the local variables (with their initial values) and the parameters. Each copy of the code includes a marker indicating the current position. When a recursive call is made, the marker in the old copy of the code is just after the call; the marker in the “cloned” copy is at the beginning of the method.

A ‘function’ is also called ‘method’ sometimes. Most people use these terms interchangeably. If you are a programming purist, I would say there is a subtle difference between a function and a method. A method is on an object where as a function is independent of an object. Coming back to the point, when the method returns, that clone goes away, but the previous ones are still there, and know what to execute next because their current position in the code was saved (indicated by the marker).

Let’s see how the machine does it

Here’s how function calls really work (be it recursive or non-recursive):

• At runtime, a stack of activation records (ARs) is maintained: one AR for each active method. When we say “active”, it means that the method has been called, but has not yet returned.
• Each AR includes space for the following: the method’s parameters, the method’s local variables, and the return address. The return address refers to the location in the code where it starts executing after the method returns.
• When a method is called, its AR is pushed onto the stack. The return address in that AR is the place in the code just after the call (so the return address is the “marker” for the previous “clone”).
• When a method is about to return, the return address in its AR is saved, its AR is popped from the stack, and control is transferred to the place in the code referred to by the return address.

Recursion vs Iteration

You may have noticed that a lot of problems that can be solved using recursion can also be solved using iteration. So why not just use iteration and avoid all the recursive code and its associated confusion? Well, let’s think about when it is a good idea to use recursion and why.

Is the recursive version usually faster? Not really. In fact, it’s usually slower due to the overhead of maintaining the stack. Does the recursive version usually use less memory? No, it usually uses more memory, again because of the stack. So why on earth do we use recursion? Its because sometimes it is much simpler to write the recursive version of the code. You can write the iterative equivalent of all the code we discussed in the previous post and you can see how small recursive code is as compared to the iterative counterpart!

————————————————————————————————-