# Learn How to Think with Karel the Robot. Chapter 14. Recursion

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

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.

### 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:

2def walk

3 if shield

4 get

5 go

6 # Stopping condition:

7 if not home

8 print(~Recursive call...~)

9 walk

10 print(~Recursive call ended.~)

11 return

12

13# Main program:

14print(~Calling ’walk’ from the main program...~)

15walk

16print(~Call from the main program ended.~)

### 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:

2def walk

3 if shield

4 get

5 go

6 print(~Recursive call...~)

7 walk

8 print(~Recursive call ended.~)

9 return

10

11# Main program:

12print(~Calling ’walk’ from the main program...~)

13walk

14print(~Call from the main program ended.~)

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:

2def walk

3 if shield

4 get

5 if box

6 put

7 go

8 # Stopping condition:

9 if not home

10 walk

11 return

12

13# Main program:

14walk

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:

2def sweep

3 if shield

4 get

5 if wall

6 left

7 if wall

8 right

9 right

10 go

11 # Stopping condition:

12 if not home

13 sweep

14 return

15

16# Main program:

17sweep

### 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:

2def move

3 if wall

4 left

5 if wall

6 right

7 right

8 go

9 # Stopping condition:

10 if not home

11 collect

12 return

13

14# Recursive command:

15def collect

16 if shield

17 get

18 # Stopping condition:

19 if not home

20 move

21 return

22

23

24# Main program:

25move

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:

2def sum(n)

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:

14 else

15 # Return 1:

16 print(~Recursion ended, returning 1~)

17 return 1

18

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:

### 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:

2days = [’Mon’, ’Tue’, ’Wed’, ’Thu’, ’Fri’, ’Sat’, ’Sun’]

3

4# Recursive function to parse a list:

5def parselist(L)

6 if len(L) != 0

7 print(L[0])

8 parselist(L[1:])

9 return

10

11# Main program:

12parselist(days)

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:

2nums = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

3

4# Recursive function to add all items in a list:

5def add(L)

6 if len(L) > 0

7 s = add(L[1:])

8 return s + L[0]

9 return 0

10

11# Main program:

12result = add(nums)

13print(~The result is:~, result)

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.

QUESTION 14.1. In which areas can one encounter recursion?

- A
- Art
- B
- Nature
- C
- Mathematics
- D
- Computer programming

QUESTION 14.2. Which of the following activities can be viewed as recursion?

- A
- Eating your lunch.
- B
- Cleaning your room.
- C
- Reading a book.
- D
- Counting down from 10 to 1.

QUESTION 14.3. What is characteristic for tasks which are suitable for recursion?

- A
- They are repetitive.
- B
- They require variables.
- C
- They require lists.
- D
- They can be reduced to the same task, but smaller in size.

QUESTION 14.4. Where should the recursive call be made?

- A
- At the beginning of the command or function.
- B
- At the end of the command or function.
- C
- From the body of a stopping condition.
- D
- Before a stopping condition.

QUESTION 14.5. What happens if one forgets the stopping condition?

- A
- The program will run forever or crash.
- B
- Recursion will turn into an infinite loop.
- C
- The recursive call will not be executed.
- D
- The recursive call will be only made once.

QUESTION 14.6. What does it mean that two commands A and B and mutually recursive?

- A
- A is recursive and B is not.
- B
- B is recursive and A is not.
- C
- A calls B and B calls A.
- D
- A calls itself and B calls itself.

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