Learn Recursion Like You are 5

Published in

Technology Hits

8 min readOct 9, 2020

Recursion can be a difficult concept to grasp. For most people, the idea of a function calling itself is nothing to wrap one’s head around. Here, I use a simple analogy to explain some of the key components of recursion. This is for someone who is new to the concept or uses recursion but does not seem to understand the whole idea of it.

Let’s say there is a person called Steve.
So Steve was given some oranges to sell. But Steve is so lazy that he does not want to sell all the oranges right away.
Steve noticed that he can sell a small number of these oranges right away and leave the rest of the selling for tomorrow. Below is the image of the oranges Steve is to sell:

A is the set of oranges Steve agreed to sell for the day.
B is the rest of the oranges that Steve will leave for tomorrow.

So Steve made N10 from selling the A part of the oranges. You would agree with me that Steve will have to keep that N10 somewhere until he is able to sell the rest of the oranges. Only then will he combine the sales and return back to mummy.

Day 2

When tomorrow came, Steve noticed that the task for today is looking like that of yesterday except simpler (i.e selling the leftover from yesterday). That is so because he already sold part of the oranges yesterday:

However, these oranges cannot fit the tray anymore, because the sale from yesterday has left a vacuum that oranges are now falling over. This necessitated steve to buy a more befitting tray, a smaller one:

But he is still lazy today so he figured, “why not break the task into two like I did yesterday(i.e sell a part of these oranges and leave the rest for the next day)”

And he got a part of the oranges to sell, leaving the rest for the next day:

And by the end of the day, Steve is left with:

Day 3

On day 3, Steve had to get a new tray to fit the new size of oranges:

Steve has not changed from his lazy ways even for the third day. He only sold a part of the oranges and left others for tomorrow:

Day 4

After he sold G part of the oranges, he is left with:

Day 5

On Day 5, Steve had the below oranges to sell:

By the end of the day, Steve was left with an empty tray.

Day 6

On Day 6, Steve was dump enough to take the empty tray from yesterday to the market. However, because he has no more oranges to sell, He had to come back with N0, unlike the other days that he will sell more than that. Interestingly for Steve though, he will not have to go to the market tomorrow, because now he knows that he has no oranges to sell.

There is something that needs to be done, however. Steve has to add all the pieces of sales he made in each of these days and return it back to mummy as a single sale.

The easiest way to do this is to start summing the sales from the last day. If Steve chooses to go the other way (start from the first day), he will run into an issue. On the first day, he will be unaware of what the price might be for the rest of the oranges. But starting from the last day means all the oranges have been sold, and all the sales can now be determined.

So:

For the oranges left on Day 6 (last day), the sales = ₦0
Sales from Day 5 to the last day = ₦10 + 0 (from yesterday)= ₦10
Sales from Day 4 to the last day = ₦10 + ₦10 = ₦20
Sales from Day 3 to the last day = ₦10 + ₦20 = ₦30
Sales from Day 2 to the last day = ₦10 + ₦30 = ₦40
Sales from the first day (Day 1) to the last day = ₦10 + ₦40 = ₦50

Steve was happy he made ₦50 and he returned it back to mummy smiling.

We can represent Steve’s task for the day as a function.

We know that Steve receives several oranges to sell each day.
He sells 8 oranges each day for ₦10
He then sells the rest of the oranges in the coming days
Then he adds the sale for today with the rest of the sales and returns back to mummy.

Let us call that function sell_oranges():

function sell_oranges(int oranges) {    int sales_for_today = 10;
    int oranges_sold_today = 8;    int oranges_for_tomorrow = oranges - oranges_sold_today;    return sales_for_today  +   sell_oranges(oranges_for_tomorrow);}

If you followed the analogy used from the start, then the function above should be fairly understandable. The last line returns the sum of our sales for the day and whatever we get from selling the rest of the oranges for tomorrow. But there was a day Steve had to stop going to the market. This was the day he went to the market with an empty tray. Our function did not really handle that scenario. So we need to check if the oranges sent for Steve to sell are less than 1. If so, the sale for that day will only be 0:

function sell_oranges(int oranges) {    if(oranges < 1) {
       return 0;
    }    int sales_for_today = 10;
    int oranges_sold_today = 8;    int oranges_for_tomorrow = oranges - oranges_sold_today;    return sales_for_today  +   sell_oranges(oranges_for_tomorrow);}

Why is recursion so difficult to grasp sometimes?

If you ask me, the most challenging thing about recursion is the idea of “calling a method within itself.” How is that possible, right? From our code above, we can see that the function sell_oranges is called within its own definition. This is the root of all misunderstandings.

But coming back to our analogy. If you look carefully at how Steve sells these oranges, you will agree with me on one thing. Even though every day seems to be a repetition of the previous day, these days are unique and different in their own right. For one, every day comes with a simpler, smaller size(number) of oranges. Also, yesterday might be Tuesday and today Wednesday. Even though the events might be the same, the days are different entities on their own.

And this is how the computer sees things. When we make recursive calls, the computer doesn’t call the same method that is already running. Instead, the computer makes a copy of this method and passes the simpler problem to solve with. This copy is treated differently as if it were a different method altogether. So the function is not really calling itself but calling a copy of itself.

What are the downsides of using recursion?

If you remember, Steve has to buy a new tray each day because the one from yesterday couldn’t fit the remaining oranges. This means that every day has to maintain its own tray. By the end of the last day, Steve must have used quite many trays. Such a waste, right?

Because we make a copy for every recursive call, each copy will maintain its own variables, eating up valuable space. And how much space we take will depend on the number of recursive steps we take. Just like the number of plates wasted depends on the number of days used in selling the oranges, which ultimately depends on the size(number) of the oranges Steve needs to sell.

So, whenever you want to implement a recursive solution, you might want to keep that in mind.

One pitfall to avoid

When defining recursive functions, always remember to include a base case. In the example with Steve, we make sure we don’t go to the market again when the tray is empty. So the base case is when the oranges are 0 or less. If we don’t put a check on that, Steve will keep on going to the market with that empty tray forever. The case where we need to stop is called the base case. Without the base case, the recursive function will keep calling copies of itself until we run out of memory and experience a StackOverflow. It is important to note that a recursive function can have more than one base case.

Takeaways

Recursion is the concept of breaking a problem into smaller and simpler versions, where solving a bigger problem will depend on the solution of a smaller version of that problem.
The overall solution to the said problem will be the total of the solutions to these smaller subproblems.
Solving a smaller subproblem follows the same process as solving the bigger one.
A recursive function will have a base case where we don’t need to make recursive calls anymore but return an actual value back. This prevents our function from running forever.
From the computer’s standpoint, a recursive function does not call itself but a copy of itself, which is treated as a different function altogether.
Each recursive call consumes its own memory. This means that for n recursive calls, we waste n space. Hence, recursive solutions always have O(n) space complexity as opposed to iterative solutions.
Because method calls are treated in a stack-like fashion, the last recursive call will be the first to release its resources as it returns back. And it continues in this manner until we reach the first call.

As an exercise, write a recursive function that computes the sum of the first nth natural numbers. This means that if 2 is passed to your function, it should return 3 as the solution (because the sum of the first 2 natural numbers is 1 + 2 = 3).