Suppose you're digging through your grandma's attic and come across a mysterious 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 key is in a box somewhere.
What's your algorithm to search for the key?
In this unit you'll learn about recursion. Recursion is used in many algorithms, and is a building block for
understanding later units in this course.
Recursion can be used to solve the previous problem of searching for a key in nested boxes.
You will also learn to break down a problem into a base case and a recursive case.
I will be showing you a lot of code examples.
I highly recommend trying to run the code for yourself.
Also,
At least once you should try to step through a recursive function with pen and paper
to get a better sense of how recursive functions work. This unit also includes a lot of pseudocode.
Pseudocode is a high-level description of the problem you're trying to solve in code.
It's written like code, but it's meant to be closer to human speech.
Let's get back to searching for a key in a box that contains boxes which contain other boxes.
First, I'll show you a method to solve this problem that uses while loops.
Then, I'll show you a method that uses recursion.
Here's the first method. 1- Make a pile of boxes to look through.
2- While the pile is empty, grab a box and look through it.
3- If you find a key, you're done!
4- If you find a box, add it to the pile of boxes to look through later.
5- Repeat.
Here's the second method. 1- Look through the box.
2- If you find a key, you're done!
3- If you find a box, go to Step 1.
Which approach seems easier to you? The first way uses a while loop.
Here's the first method using pseudocode.
First, we make a pile of boxes to look through, from the boxes in the main box.
While the pile is not empty, choose a box to look through.
For each item in the box, check if the item is another box. If it is another box,
append, or add it to the pile of boxes
we still have to look through. If the item we found is a key, then yell to everyone excitedly, "found the key!"
Keep checking the boxes until the pile is empty.
The second way uses recursion. Recursion is where a function calls itself.
Here's the second way in pseudocode.
First, we check the box passed into the function, and go through each item in the box.
If the item is a box, then we pass the box into the function again.
If the item is a key then yell to everyone excitedly, "found the key!"
Both approaches accomplish the same thing, but the second approach seems cleaner.
A recursion is used when it makes the solution clearer.
There's actually no performance benefit to using recursion- in fact, loops are sometimes better for performance.
However, people still use recursion since it often makes code easier to understand and look cleaner.
Many important algorithms use recursion, so it's important to understand.
Because a recursive function calls itself, it's easy to write a function incorrectly, that ends up in an infinite loop.
For example, suppose you want to write a function that prints a countdown.
You could write it recursively, like this:
However, if you run this code, there's a problem. The function will run forever.
If your code is in an infinite loop, press control+C to kill the script.
When you write a recursive function, you have to tell it when to stop recursing.
That's why every recursive function has two parts: the base case and the recursive case.
The Recursive case is when the function calls itself. The base case is when the function doesn't call itself again,
so it doesn't go into an infinite loop. Here is the function from before, with the addition of a base case.
The "if i is less than or equal to 1", is the base case.
That is when the function will not call itself anymore. In the "else" section is the recursive case.
That is what will keep happening if the base case has not yet been reached.
So, unlike the last example, this function will actually end.