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.

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

picture

Let’s see some examples, starting with the famous Russian dolls:


PIC

Figure 14.1: *

Russian dolls - an example of recursion in art.


Snowflakes are an example of recursion in nature:


PIC

Figure 14.2: *

A snowflake.


Fractals are mathematical objects which exhibit recursion. The following is an example of the Julia fractal:


PIC

Figure 14.3: *

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


PIC


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


PIC


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


PIC


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:


PIC

Figure 14.4: *

Collect all shields!


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.


PIC

Figure 14.5: *

After one step, Karel’s task is the same: Collect all shields!


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

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:


PIC


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:


PIC

Figure 14.6: *

The sequence of recursive calls.


picture

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:


PIC


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


PIC


picture

14.6. Moving shields to boxes

Today Karel needs to use recursion to put the shields in the boxes, instead of just collecting them:


PIC

Figure 14.7: *

Move the shields to the boxes!


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:


PIC

Figure 14.8: *

Sweep the floor and collect all shields!


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


PIC


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:


PIC


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

Created on September 27, 2018 in Karel.
Add Comment
0 Comment(s)

Your Comment

By posting your comment, you agree to the privacy policy and terms of service.