Understanding Recursion With Examples
Photo by Josip I. on Unsplash.
What is recursion?
Open a browser and type “recursion” on Google. Did you notice the “Did you mean: recursion” message?
Photo by author. Screenshot of Google.
Click on that message. It will appear again. Click again. There it is again. Click it… OK, enough.
You’re now beginning to understand what recursion is. If you scroll down on that very same Google page, you will see this:
“Recursion: the repeated application of a recursive procedure or definition.”
Even recursion’s own definition is recursive.
Recursion in Programming
In programming terms, recursion happens when a function calls itself.
If you have a problem that is too complex, you can use recursion to break it down into simpler blocks. You do this in real life all the time. Imagine you have a whole box full of $100 bills and you need to count how much money you have. Since it’s a lot, you might ask for the help of your friend, and you divide the stack in two. When you both finish counting, you add up your results and get the final number.
It would be the exact same total if only one of you counted it all — you just took a different road. In programming, this road is called recursion, and the alternative road is called iteration.
So when should you use one or the other?
Why Use Recursion?
Recursion is preferred when the problem can be broken down into smaller, repetitive tasks. These are the advantages of using recursion:
- Complex tasks can be broken down into simpler problems.
- Code using recursion is usually shorter and more elegant.
- Sequence generation is cleaner with recursion than with iteration.
But you should not use recursion every time just because it is possible to do so.
Why Not to Use Recursion
Even though there are times when recursion is the best solution, it is not commonly used because:
- The recursive logic is usually harder to follow and debug.
- It increases memory usage and its Big O notation is often higher than the corresponding iterative solution. This means that recursion can be great for smaller programs but might lead to memory problems in bigger projects.
How to Use Recursion
Now that we’ve established when to use recursion and when not to, let’s have a look at how we can implement it.
A recursive function requires two parts: a recursive call and a base case.
The recursive call is the part of the function that will keep calling itself.
The base case returns a value without making any subsequent calls. The function might have more than one base case, but it must have at least one. If not, your function will enter an infinite loop and your program will crash.
Examples
Finally, let’s put the theory into practice. Let’s take a classic example where recursion is the best solution: the Fibonacci sequence. If we want to generate the nth Fibonacci number using recursion, we can do it like this:
Much cleaner than when compared to the iterative solution:
Let’s take another example. In this case, we have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively. We could do it like this:
