Learn How to Think with Karel the Robot. Chapter 14. Recursion
In this chapter you will learn:
- What recursion is and why it is useful.
- How to recognize whether or not a task is suitable for recursion.
- How to implement recursion correctly.
- What can happen if recursion is not done right.
- How to use variables, lists, and functions in recursion.
- About mutually recursive commands and functions.
At the end, we will show you examples of tasks which can easily be solved with recursion, but which would be extremely difficult to tackle without it.
When you try to learn about recursion, you will come across statements like this:
Let’s see some examples, starting with the famous Russian dolls:
Snowflakes are an example of recursion in nature:
Fractals are mathematical objects which exhibit recursion. The following is an example of the Julia fractal:
In the following section we will give examples of tasks which are suitable for recursion.
All recursive tasks have one thing in common: Part of the task can be solved by some method.
The rest is then a smaller copy of the same task. So, one can solve part of it using the same
method as before. The rest will then be a smaller copy of the same task. So, one can solve part of
it using the same method... etc.
Example 1: Eating your lunch is a recursive task
Imagine that your "task" is to eat your food. If you don’t like chili, picture your favorite food
now. How do you eat it? Well, first you check: Is there any more left? If so, you eat a bite. Then
there is a bit less food to eat. So you check: Is there any more left? If so, you eat a bite. Then there
is a bit less food to eat...
Example 2: Cleaning up is a recursive task
Your next task is to put all the Lego pieces back in the box. First you check the floor: Are there
some pieces still lying around? If so, collect a few and put them in the box. Then there are fewer
loose pieces on the floor. So you check: Are there some pieces still lying around? If
so, collect a few and put them in the box. Then there are fewer loose pieces on the
Example 3: Reading a book is a recursive task
Our third and last example is about reading a book. Your progress will be measured by the number of unread pages. First you check: Are there any more pages left to read? If so, read a few pages from where you left off. After that, fewer pages remain, so your task got smaller. So you check: Are there any more pages left to read? If so, read a few pages from where you left off. After that, fewer pages remain, so your task got smaller...
Today, Karel’s task is to collect all shields and enter the home square:
The recursive algorithm for Karel to do this is as follows:
- If you are not home:
- If there is a shield beneath you, collect it.
- Make one step forward.
- After this, the task is the same, just smaller: Collect all shields!
Notice the condition "if you are not home" at the beginning. This condition is very important in recursion. It is called the stopping condition. When one forgets it, recursion instantly turns into an infinite loop.
And here is the corresponding code. Notice that after collecting one shield and moving one step forward, the command walk calls itself on line 9. Also, notice that the recursive call on line 9 is made from the inside of a stopping condition ifnothome. This means that when Karel arrives at home, the command walk is not called anymore and the recursion ends:
3 if shield
6 # Stopping condition:
7 if not home
8 print(~Recursive call...~)
10 print(~Recursive call ended.~)
13# Main program:
14print(~Calling ’walk’ from the main program...~)
16print(~Call from the main program ended.~)
The last program contained some control outputs to help us understand the program flow better. Let’s have a look at them:
The first line corresponds to calling walk on line 15 in the main program. The second line corresponds to executing walk on line 9 of its own body. At this point, a new copy of the command walk is created in the computer memory and called. The original command walk which was called on line 15 is put on hold.
To make the explanation simpler, let’s name the new copy walk2 (although in reality the names do not change like this). The command walk2 executes walk on line 9 again. This creates a new copy of the command walk which we can name walk3. The new copy walk3 is called and the copy walk2 is put on hold.
This process continues and other three copies walk4, walk5 and walk6 are created and called. Finally, in walk6, Karel enters the home square and therefore the stopping condition on line 7 is not satisfied. Therefore, the program goes directly to line 11 and walk6 ends.
At this moment, the control is returned to walk5 where the program continues on line 10 and displays for the first time the message Recursivecallended. The program then goes to line 11 and walk5 ends. Then the control is returned to walk4 where the program continues on line 10, and displays for the second time the message Recursivecall ended.
This process continues until walk2 ends and the control is returned to the original command walk. When this command ends, control is returned to the main program, and the last message is displayed: Callfromthemainprogramended. Here is the sequence of the recursive calls in graphic form:
Forgetting to place the recursive call in the body of a stopping condition leads to an infinite loop - the recursion never stops. Let’s illustrate this by removing the stopping condition from the previous program:
3 if shield
6 print(~Recursive call...~)
8 print(~Recursive call ended.~)
11# Main program:
12print(~Calling ’walk’ from the main program...~)
14print(~Call from the main program ended.~)
Here is the corresponding output:
Today Karel needs to use recursion to put the shields in the boxes, instead of just collecting them:
The program is similar to the previous one. We only removed the control outputs and added a new condition on lines 5 and 6:
3 if shield
5 if box
8 # Stopping condition:
9 if not home
13# Main program:
Again, notice that the recursive call on line 10 is made from the body of a stopping condition ifnothome which guarantees that the recursion stops when the robot gets to his home square.
Someone stole from the museum historical items of immense value, and left some shields lying scattered on the floor. Karel needs to sweep the floor for any traces, collect the shields, and bring them to the home square:
Here is the corresponding program. You will recognize the First Maze Algorithm on lines 5 - 10:
3 if shield
5 if wall
7 if wall
11 # Stopping condition:
12 if not home
16# Main program:
In recursion, a command or function does not always have to call itself. Recursion also occurs when command A calls command B, then command B calls command A, then command A calls command B, etc. Let’s illustrate this on the previous example, where we decompose the recursive command sweep into a pair or mutually recursive commands move and collect:
3 if wall
5 if wall
9 # Stopping condition:
10 if not home
14# Recursive command:
16 if shield
18 # Stopping condition:
19 if not home
24# Main program:
So far we have discussed recursive commands which did not involve variables. Now we will
show you that variables and functions can be used in recursion as well.
For illustration, let’s write a recursive function sum(n) to add the numbers n, n-1, n-2, ..., 1 and return the result. The idea is that if n > 1 then the function will call s = sum(n-1) and return s + n. If n == 1 then the function will return 1:
3 # Stopping condition:
4 if n > 1
5 # Calculate the rest of the sum:
6 print(~Calling ’sum’ from ’sum’ with argument~, n-1)
7 s = sum(n-1)
8 # Add n to the rest of the sum:
9 print(~Adding~, n)
10 inc(s, n)
11 # Return the sum:
12 return s
13 # Else branch of the stopping condition:
15 # Return 1:
16 print(~Recursion ended, returning 1~)
17 return 1
19# Print result for a sample value 10:
20print(~Calling ’sum’ from main program with argument 10~)
21num = sum(10)
22print(~Final result =~, num)
The recursive call on line 7 evaluates the sum of the numbers n-1, n-2, ..., 1 to which is then
added n on line 10, and the result is then returned on line 12.
Notice that the stopping condition has the form ifn > 1 which ensures that the recursion stops when n reaches 1. The function contains some control prints to help us better understand the program flow. This is the output which shows that everything went as expected:
2days = [’Mon’, ’Tue’, ’Wed’, ’Thu’, ’Fri’, ’Sat’, ’Sun’]
4# Recursive function to parse a list:
6 if len(L) != 0
11# Main program:
That was too simple, so here is one more task: Write a recursive function add(L) to add all items in a list L! But you already understand recursion really well, so this can’t throw you off balance:
2nums = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
4# Recursive function to add all items in a list:
6 if len(L) > 0
7 s = add(L[1:])
8 return s + L
9 return 0
11# Main program:
12result = add(nums)
13print(~The result is:~, result)
The result is 110. Add the numbers yourself to verify it’s true!
All the examples that we have presented so far were easily solvable without recursion as well. So, you might get an impression that all tasks which can be solved with recursion can easily be solved without it. But that would not be true. The problem with demonstrating the real advantages of recursion is that one needs more difficult tasks for that.
Therefore, we prepared for you three such tasks. All of them can be solved easily with recursion but they would be much more difficult to tackle without it. You will find them in Section 15.1 (page 1279), Section 15.2 (page 1286) and Section 15.3 (page 1290).
Friendly reminder - for every question either none, one, or several answers may be correct.
- Computer programming
- Eating your lunch.
- Cleaning your room.
- Reading a book.
- Counting down from 10 to 1.
- They are repetitive.
- They require variables.
- They require lists.
- They can be reduced to the same task, but smaller in size.
- At the beginning of the command or function.
- At the end of the command or function.
- From the body of a stopping condition.
- Before a stopping condition.
- The program will run forever or crash.
- Recursion will turn into an infinite loop.
- The recursive call will not be executed.
- The recursive call will be only made once.
- A is recursive and B is not.
- B is recursive and A is not.
- A calls B and B calls A.
- A calls itself and B calls itself.
Table of Contents
- 1. Introduction
- 2. Basic Commands
- 3. Counting Loop
- 4. Conditions
- 5. Conditional Loop
- 6. Custom Commands
- 7. Variables
- 8. Functions
- 9. Text Strings
- 10. Testing Your Programs
- 11. Boolean Values, Variables, Expressions, and Functions
- 12. Randomness and Probability
- 13. Lists
- 14. Recursion
- 15. Advanced Applications
- Appendix A. Karel App in NCLab
- Appendix B. Self-Paced Karel Course in NCLab