Recursion — what it is, and how memory is handled in the process
- While this article uses an example with the C progrmaming language, the concepts in it are applicable to other languages that have access to recursive logic
- You should at least be familiar with basic programming concepts like loops, if statements, and some familiarity with a function and its parameters.
Functions
Before we can dive into what recursion itself is, it’s important to think about what a function is, what it’s for, and how their return values work.
When writing a program, there will come times where you will find yourself needing to perform a set of actions multiple times, accross different parts of your code. A beginner may make the mistake of writing that repetitive code again (or copy-pasting it) each time they need to perform an action. But copy-pasting code is pretty much always going to be bad practice. If a bug with that sequence were to occur, or a change would need to be made, you would have to manually search through every single instance of that set of actions and repeat the change everywhere. This is a breeding ground for human error.
This is where functions come in. It allows you to place those actions in one place, and you can simply call the function whenever you need to perform the action. Though there is one more concept that we need to be familiar with if we want ot make propper use of these functions.
The Stack
The way that memory is handled when dealing with functions can be confusing at first. Let’s look at this simple code example of a function that adds two values together.
The code is simple. It declares two local variables (x, y) with each one being equal to five. It will print the value of X before any changes made. Then it calls the “add” function, which takes the two values and adds b to a. Finally it prints x again . If you’re familiar with how the stack works, you’ll immediately spot the problem.
Output:
What happened?
Whenever a function is called, the memory that is created for that function is created on the stack. The stack is an area of a computer’s memory which stores all the temporary variables in a function. This memory has a Last-in-First-Out (LIFO) structure. When a function is called, the variables that are declared inside that function are stored on the top of the stack.
When we called add() from the main function and passed our variables to it, new memory was created, and copies of the variables were created. And our program will be accessing the memory that is on the top of the stack.
What this means is that, even though we assigned the variables x and y to the parameters of add(), we really created a copy of these variables. And because of the LIFO structure, when we try to access the variables, we can only access the copy. So when we do a += b, we perform these on the memory created for the add() function. which is erased after the function is done.
But what do we do if we want to do something with the data that we got from the add() function? This is where return values come in. When a function has a return statement, it returns the value to the function that called it, and if you assign this returned value into a local variable from the calling function (in this case main), you can do things with it.
Let’s make some changes.
Now, we return the result of the addition of the two parameters, and assign it to x. This way we overwrite x with the result of the addition. So when we run the program…
Output:
We see that we were able to do what we wanted. Great.
So, what is recursion?
Recursion, at its simplest form, is a function that calls itself. So in a way, it can be comparable to a loop. However, With regular loops, you can visualize each iteration and go one step at a time. But with recursion, you may find yousrelf going to the very end of the process first, before rolling back around to perform each step.
The following function calculates x^y. so x * x, and you perform this y times. To do this calculation, you need to get the result of the previous calculation, and multiply it by x.
Example:
5³ = (5 * 5 * 5) = 125
step by step it would be:
(5 * 5) = 25
25 * 5 = 125
Now let’s look at how we can do this recursively:
Let’s ignore the first two if statements at first. We have our variables x and y. X is the number we want to multiply Y times. If we look at the last return statement first. As you see, the function calls itself, but each time it does, it passes y - 1. This means that each time we call the function, y is getting closer to 0. The same thing happens if the number is negative, but in reverse, y + 1.
Once y = 0, we can get our first result, which is x⁰, which will always be equal to 1. So we just return 1 to the previous call of the function. And now the rest of the code that comes after each call gets to execute, which is:
(previous return value) * x
It’s difficult to grasp at first without any visualization. So let’s take a look at this drawing my partner Christopher drew up for me showing this process:
Each pipe represents the function call: pow_recursion(x, (y - 1)
Y gets progressively closer to 0, and once it reaches 0, it goes through with the first calculation, x⁰, which is 1. Then it gets sent back up to the previous call, where the calculation (previous * x) gets done, until finally the whole process ends, and we get our result.
Recursions suck
Sort of. They have their purpose. Whenever you need to perform some sort of calculation or algorithm that is dependant on a previous result, they can be very helpful. However, recursions can be very expensive when it comes to memory and processing power. Because of the stack.
Remember, whenever we call a function, the memory gets created for each variable in that function and added to the stack:
No big deal, but for each subsequent recursive call to that function, more memory gets added to the stack, and this can be very ineficient:
So if you’re not careful you could end up with performance issues as more and more memory is used, which can become pretty disastrous if you’re dealing with a bigger application.
Okay, so the answer is…
Recursion is a function that calls itself. As for all functions, the memory for these functions is stored on the stack, which has a LIFO (Last-in-first-out) structure, where the program can only access the local variables stored on the top of the stack. It can be useful for mathematical equations or algorithms that are dependant on the previous results of the calculation. And finally, we should be very aware of its expensive memory usage that can cause performance issues.
