Home

Introduction to Python Programming. Section 17. Recursion

17 Recursion

17.1 Objectives

In this section we will show you:

  • That recursion is a concept that extends way beyond computer programming.
  • 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.

17.2 Why learn about recursion?

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

17.3 Introduction

Many websites describe recursion more or less as follows:

  • "Programming technique where a function can call itself..."
  • "The process in which a function calls itself..."

But recursion is much more. It can be found in many areas ranging from art and linguistics to mathematics and computer science. The following image shows an example of recursion in art: – the so-called Russian dolls.

PIC


Fig. 74: Russian dolls - an example of recursion in art.

Notice that they are all very similar, almost identical, just getting smaller and smaller. In fact, they can be inserted in each other so that at the end the largest one contains all of them.

17.4 Is your task suitable for recursion?

Let’s talk about using recursion to solve certain tasks. An important skill that you need to acquire is to recognize whether a task is suitable for recursion or not. All tasks which are suitable for recursion are similar:

  • Part of the task can be solved by any method.
  • The rest leads to exactly the same task, just smaller.
  • Typically, recursive tasks are repetitive in nature.

Let’s show a few examples.

Example 1: Eating your lunch is recursion

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. But you can start the original task again: Eat your food!

PIC


Fig. 75: Eating your lunch is recursion.

Example 2: Cleaning up is recursion

Your next task is to put all the Lego pieces back into the box. First you check the floor: Are there some pieces still lying around? If so, collect a few and put them into the box. Then there are fewer loose pieces on the floor. So your can start the original task again: Put all the Lego pieces back into the box!

PIC


Fig. 76: Cleaning up is recursion.

Example 3: Reading a book is recursion

The 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. But it is still the same: Read the rest of the book!

PIC


Fig. 77: Reading a book is recursion.

17.5 Calculating the factorial

The factorial n! of a positive integer n is the product n ⋅ (n - 1) ⋅ (n - 2)…2 ⋅ 1, and moreover the factorial 0! is 1. This is a perfect task for recursion because n! is n ⋅ (n - 1)! which means that the task can easily be reduced to the same task, just smaller. Here is the corresponding Python code, with a sample calculation of 5! at the end:

  def factorial(n):
      if n > 0:
          return n * factorial(n-1)
      return 1
  
  print(factorial(5))

  120

On line 3, the function factorial calls itself – this is the recursive call. For every recursive call, a new copy of the function is created in computer memory.

The program looks extremely simple, but there is one important thing which is easy to miss – notice that the recursive call is made from the body of a stopping condition. Every recursive algorithm needs a stopping condition. Without one, it instantly turns into an infinite loop. In fact, obtaining an infinite loop is the most frequent bug in the design of recursive algorithms. We will talk about it in more detail in the next subsection.

But before we get there, let’s take a closer look at the previous program. In order to gain more insight into what is happening inside, we will add some debugging prints into it. First let’s run the program, and then we will discuss the output:

  def factorial(n):
      if n > 0:
          print(~Calling factorial(~ + str(n-1) + ~)~)
          fact = factorial(n-1)
          print(~Obtained factorial(~ + str(n-1) \
          + ~) which is ~ + str(fact))
          print(~Returning ~ + str(n) + ~ * factorial(~ \
          + str(n-1) + ~) which is ~ + str(n*fact))
          return n * fact
      print(~Recursion finished.~)
      return 1
  
  print(factorial(5))

  Calling factorial(4)
  Calling factorial(3)
  Calling factorial(2)
  Calling factorial(1)
  Calling factorial(0)
  Recursion finished.
  Obtained factorial(0) which is 1
  Returning 1 * factorial(0) which is 1
  Obtained factorial(1) which is 1
  Returning 2 * factorial(1) which is 2
  Obtained factorial(2) which is 2
  Returning 3 * factorial(2) which is 6
  Obtained factorial(3) which is 6
  Returning 4 * factorial(3) which is 24
  Obtained factorial(4) which is 24
  Returning 5 * factorial(4) which is 120
  120

The first call to the function occurs on the last line of the program as factorial(5). With n = 5 the condition on line 2 is satisfied, and therefore the function calls itself on line 4 as factorial(4).

At this moment, a new copy of the function is created in computer memory and the value of n is 4. Then again, the condition on line 2 (of the copy) is satisfied, and the function calls itself on line 4 as factorial(3).

At this moment, a new copy of the function is created in computer memory and the value of n is 3. This goes on until a new copy of the function is created and the value of n is 0.

This is a very important moment because the condition on line 2 is not satisfied. Hence the fifth recursive copy of the function displays ~Recursion finished~, returns 1, and ends.

At this moment, we are back on line 4 of the fourth recursive copy of the function, with fact = 1. The rest of the body of the condition is executed, and because fact = 1 and n = 1, the return statement returns 1. Then the fourth recursive copy of the function ends.

At this moment, we are back on line 4 of the third recursive copy of the function, with fact = 1. The rest of the body of the condition is completed, and because fact = 1 and n = 2, the return statement returns 2. Then the third recursive copy of the function ends.

This goes on until also the second and first recursive copies of the function are finished, and finally, also the main call to the function on the last line of the program ends.

17.6 Stopping condition and infinite loops

To illustrate the importance of the stopping condition, let us remove it from the previous program:

  def factorial(n):
      print(~Calling factorial(~ + str(n-1) + ~)~)
      fact = factorial(n-1)
      print(~Obtained factorial(~ + str(n-1) \
      + ~) which is ~ + str(fact))
      print(~Returning ~ + str(n) + ~ * factorial(~ \
      + str(n-1) + ~) which is ~ + str(n*fact))
      return n * fact
      print(~Recursion finished.~)
      return 1
  
  print(factorial(5))

Then, a new copy of the function is automatically created on line 3, which means an infinite loop. Here is the corresponding output

  Calling factorial(4)
  Calling factorial(3)
  Calling factorial(2)
  Calling factorial(1)
  Calling factorial(0)
  Calling factorial(-1)
  Calling factorial(-2)
  Calling factorial(-3)
  ...
  [OUTPUT TRUNCATED]

Python then throws a RecursionError:

  Traceback (most recent call last):
    File ~<string>~, line 10, in <module>
    File ~<nclab>~, line 3, in factorial
    File ~<nclab>~, line 3, in factorial
    File ~<nclab>~, line 3, in factorial
    [Previous line repeated 987 more times]
    File ~<nclab>~, line 2, in factorial
  RecursionError: maximum recursion depth exceeded while
  getting the str of an object

17.7 Parsing binary trees

Unfortunately, most examples which are used to explain recursion are so simple that they can be solved more naturally without recursion. For example, the factorial from the previous subsection can be calculated non-recursively using a simple for loop:

  def factorial(n):
      result = 1
      for i in range(2, n+1):
          result *= i
      return result
  
  print(factorial(5))

  120

The beauty and power of recursion shows itself in more advanced applications. One of such applications are binary trees.

PIC


Fig. 78: Sample binary tree.

A binary tree "grows" from the top down. The circles are called nodes. Each node contains a number, and it can have up to two branches (hence the name binary tree). The number of levels in called depth – the sample binary tree in Fig. 78 has depth 4. Usually, the shape and depth of the binary tree are unknown.

One way to represent such a binary tree in Python is using embedded lists. Each node is a three-item list where the first item is the number, the second item is the left branch, and the third item is the right branch. An empty list is used for an empty branch. Let’s show some examples.

In Fig. 78, the node with the number 2 is without branches, and therefore it is represented as [2, [], []]. The other nodes without branches just differ in the number. The node with the number 9 only has the left branch, and therefore it is represented by the list [9, [4, [], []], []]. The node with the number 6 has both branches, and therefore it has the form [6, [5, [], []], [11, [], []]]. The entire tree can then be written as [2, [7, [2, [], []], [6, [5, [], []], [11, [], []]]], [5, [], [9, [4, [], []], []]]].

Now imagine that our task is to parse such a binary tree and add all the numbers. This would be extremely difficult without recursion. On the other hand, a recursive algorithm is very simple:

  • The list (let’s call it t) has three items t[0] (the number), t[1] (the list representing the left branch), and t[2] (the list representing the right branch).
  • If t is empty, return 0.
  • Otherwise add to the value t[0] all values in the left branch t[1] and all values in the right branch t[2], and return the result.

This is the corresponding code. Take a minute to verify that indeed all the values in the tree from Fig. 78 add up to 51!

  def addtree(t):
      ~~~
      Add recursively all values in a binary tree.
      ~~~
      if t != []: return t[0] + addtree(t[1]) + addtree(t[2])
      return 0
  
  # Main program:
  T = [2, [7, [2, [], []], [6, [5, [], []], [11, [], []]]], [5,
      [], [9, [4, [], []], []]]]
  print(addtree(T))

  51

Table of Contents

Created on August 6, 2018 in Python I,   Python II.
Add Comment
Cancel
0 Comment(s)

Your Comment

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