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

## Chapter 14Recursion

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.

"To iterate is human, to recurse divine." (L. Peter Deutsch)
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:

"Programming technique where a function can call itself..."
or
"The process in which a function calls itself..."
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.

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

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

1# Recursive command:
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:

1# Recursive command:
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:

1# Recursive command:
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:

1# Recursive command:
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:

1# Recursive command:
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:

1# Recursive function to add numbers n, n-1, ..., 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:
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:

1# Sample list:
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:

1# Sample list:
2nums = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
3
4# Recursive function to add all items in a list:
6  if len(L) > 0
8    return s + L[0]
9  return 0
10
11# Main program:
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
B
C
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.