Recursion is the first topic that makes beginner programmers nervous. I had been there too. And that is expected because recursion is not a natural thing to happen in real life. It is a very abstract and mathematical concept, and that makes it a bit tricky to grasp at first. But don’t worry we wouldn’t use any advanced math here. So let’s jump into it.
Recursion meme from 9GAG
In its simplest form, a recursive function is one that directly or indirectly calls itself. Let me try to explain with an example.
Let’s take an example from grokking algorithms:
Suppose you’re digging through your grandma’s attic and come across a
mysteriously locked suitcase. Grandma tells you that the key for the suitcase is probably in this other box.
This box contains more boxes, with more boxes inside those boxes. The
the key is in a box somewhere. What’s your algorithm to search for the key?
Here are iterative and recursive approaches to find the key:
Which approach seems easier and simpler to you? The recursive approach is much cleaner.
Let’s take another example:
Suppose you’re going to someone’s house. You can describe the steps as-
- If you are at the house, stop moving.
- Take one step towards the house.
- “Go to someone’s house”
See the pattern in both examples? You do the same thing with a smaller amount. This is the main concept of recursion. You keep doing the same work but every time on a smaller amount until you can’t go any smaller or have found the answer.
Parts of Recursive Algorithm
- Base Case
- Work toward the base case
- Recursive Call
Something you have to be careful about when writing a recursive function is infinite loop. This is when the function keeps calling itself and the function never stops calling itself!
The “work toward base case” is where we make the problem smaller (e.g., divide the list into two parts, each smaller than the original). The recursive call is where we use the same algorithm to solve a smaller and simpler version of the problem. The base case is the solution to the “smallest” possible problem (For example, the base case in the problem “sort the array” would be if the array has only one element… and by definition, if the list has only one element then it’s already sorted).
Let’s see an example in Code:
Problem Statement:
Return the sum of all the numbers in an array.
Solutions:
The Sum of an array is equivalent to the => first number + sum of all other numbers
Let’s breakdown the problem-
Base Case:
if len(nums) == 1:
return nums[0]
Work towards Base Case:
return first_num + sum_of_nums(rest)
Recursive Call:
sum_of_nums(rest)
By now you’ve got a grasp of basic recursion. Now we need to understand the BRI or Big Recursion Idea. It’s an idea that’s so straightforward it will
seem like a trick, but it works.
Let’s see an example from Think Like a Programmer:
Problem Statement
The manager of DelegateCorp needs to determine which of eight customers produces the most revenue for his company. Two factors complicate this otherwise simple task. First, determining the total revenue for a customer requires going through that customer’s whole file and tallying numbers on dozens of orders and receipts. Second, the employees of DelegateCorp, as the name suggests, love to delegate, and each employee passes work along to someone at a lower level whenever possible. To keep the situation from
getting out of hand, the manager enforces a rule: When you delegate, you must do some portion of the work yourself, and you have to give the delegated employee less work than you were given.
Following the company rule on delegating work, here’s what will happen
to the six customer files. The manager will take one file and determine how
much revenue that customer has generated for the company. The manager
will delegate the other five files to the vice manager. The vice manager will
process one file and pass the other four to the associate manager. This pro-
cess continues until we reach the sixth employee, the intern, who is handed
one file and must simply process it, with no further delegation possible.
Here’s an example of how this would proceed in practice.
- MANAGER tallies the revenue for customer #0001, which is $172,000.
- MANAGER to VICE MANAGER: “The highest revenue we have seen sofar is $172,000, customer #0001. Take these five files and determine theoverall highest revenue.”
- VICE MANAGER tallies the revenue for customer #0002, which is $68,000. The highest revenue seen so far is still $172,000, customer #0001.
- VICE MANAGER to ASSOCIATE MANAGER: “The highest revenue wehave seen so far is $172,000, customer #0001. Take these four files anddetermine the overall highest revenue.”
- ASSOCIATE MANAGER tallies the revenue for customer #0003, which is$193,000. The highest revenue seen so far is now $193,000, customer #0003.
- ASSOCIATE MANAGER to ASSISTANT MANAGER: “The highest revenuewe have seen so far is $193,000, customer #0003. Take these three filesand determine the overall highest revenue.”
- ASSISTANT MANAGER tallies the revenue for customer #0004, which is$13,000. The highest revenue seen so far is still $193,000, customer #0003.
- ASSISTANT MANAGER to JUNIOR MANAGER: “The highest revenuewe have seen so far is $193,000, customer #0003. Take these two files anddetermine the overall highest revenue.”
- JUNIOR MANAGER tallies the revenue for customer #0005, which is$256,000. The highest revenue seen so far is now $256,000, customer #0005.
- JUNIOR MANAGER to INTERN: “The highest revenue we have seen sofar is $256,000, customer #0005. Take this remaining file and determinethe overall highest revenue.”
- INTERN tallies the revenue for customer #0006, which is $99,000. Thehighest revenue seen so far is still $256,000, customer #0005.
- JUNIOR MANAGER to ASSISTANT MANAGER: “The highest revenueof all customers is $256,000, customer #0005.”
- ASSISTANT MANAGER to ASSOCIATE MANAGER: “The highest revenueof all customers is $256,000, customer #0005.”
- ASSISTANT MANAGER to ASSOCIATE MANAGER: “The highest revenueof all customers is $256,000, customer #0005.”
- ASSOCIATE MANAGER to VICE MANAGER: “The highest revenue ofall customers is $256,000, customer #0005.”
- VICE MANAGER to MANAGER: “The highest revenue of all customersis $256,000, customer #0005.”
In this sample problem, the BRI is in action. How so? Each person in the chain performs the same steps on a smaller and smaller subset of the original data. It’s important to note, however, that the problems involve no recursion at all.
each employee in the management chain hands-off as much work as possible to a subordinate. The assistant manager, for example, may know the junior manager well and expect the junior manager to hand all of the files but one to the intern. However, the assistant manager has no reason to care whether the junior manager processes all of the remaining files or passes some of them off to a subordinate. The assistant manager cares only that the junior manager returns the right answer. Because the assistant manager is not going to repeat the work of the junior manager, the assistant manager simply assumes that the result returned by the junior manager is correct and uses that data to solve the overall task that the assistant manager received from the associate manager. In the problems, when employees make requests of other employees, they are concerned with what but not how.
So the Big Recursion Idea is- You just need to think about the task in hand the other tasks would be handled by themselves. That brings us back to our recursive code structure again. We just need to find the base case and a way to work towards the base case others will take care of themselves.
This is all recursion is. I hope you found this article helpful. Here are some other helpful resources to learn recursion-
Top comments (0)