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.

14.1. What is recursion and why is it useful

Recursion is a fundamental concept of computational thinking.

This classical programming quote is 100% true - recursion is a beautiful and powerful tool. On the other hand, it is important to know that as any other tool, it is suitable for some tasks but not for all.

When you try to learn about recursion, you will come across statements like this:

or Well, this is not exactly true, as we will see in Section 14.8 (page 1265). But more importantly, recursion is much more. It can be found in many areas ranging from art and linguistics to mathematics and computer science.

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.

14.2. Which tasks 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 floor...

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...

14.3. Collecting shields

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:

14.4. Under the hood

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:

---

---

14.5. Forgetting the stopping condition

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:

Here is the corresponding output:

---

---

The infinite recursion was actually interrupted when Karel stepped out of the maze and the program crashed:

---

---

14.6. Moving shields to boxes

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:

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.

14.7. Museum heist

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:

14.8. Mutually recursive commands

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:

Importantly, notice that in both commands, the recursive call occurs in a stopping condition.

14.9. Using variables and functions in recursion

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:

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:

---

---

14.10. Parsing lists using recursion

Today, Karel is given a list of text strings. His task is to parse the list without using a loop, and display all its items. This is very easy indeed:

Output:

---

---

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:

The result is 110. Add the numbers yourself to verify it’s true!

14.11. Recursion at its best

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).

14.12. Review questions

Friendly reminder - for every question either none, one, or several answers may be correct.

---

Table of Contents

• About
• 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