CS 1110 - Introduction to Programming

Starting Out with Python
Chapter 12, Recursion

Objectives:

This lesson discusses chapter 12, to introduce using recursion in a program. Objectives important to this lesson:

  1. Introduction to recursion
  2. Problem solving
  3. Examples of recursion algorithms
Concepts:
Chapter 12

Introduction to Recursion

The chapter begins with a definition, telling us that a recursive function is one that calls itself. This should strike you as being dangerous, because a function that calls itself, like a loop, needs to have a mechanism to stop doing so, otherwise it might go on forever. Example program 12-1 shows us an example of such a function. It prints a message on the screen, then calls itself. This results in an infinite recursion, because there is no reason for it to stop running more versions of itself.

The text shows us a better version of this program, example program 12-2. This version passes an argument to the function, an integer, which is received in a parameter that is passed as an argument to the same function on the next call.

message(5)

def message(times):
   if times > 0:
      print("This is a recursive function.")
      Message(times - 1)

This code defines a recursive function, because it calls itself, in this case, when it finishes running. It is a controlled recursion because each time it is called, it subtracts one from the counter that tells it to do anything. Yes, the function will call itself when times is equal to 0, but it will not print on that recursion, or call itself again because the conditional will fail, its block will not be executed that time, and the program containing the initial call would continue with its next line.

The text takes a moment to caution us that this kind of programming may be slower than running a loop to do the same thing, and that there is more overhead: storing each new function call in memory, and creating variables, arguments, and parameters. Recursion should be avoidable by using an appropriate loop, but sometimes it is the right tool, and sometimes it is easier for a programmer to write a recursive structure.

Problem Solving

To use recursion, we need to plan what it will do. In the problem above, we wanted the function to do two different kinds things: to print a message and call itself, and to print a message and not call itself. The second half of the problem is more like ordinary programming. The text explains that this part is called the base case. The part that requires the function to call itself is called the recursive or recursion case. It is the circumstance that leads to the need for recursion to begin with.

From the author's point of view, the problem starts out as being complicated by wanting a countdown. It becomes simpler with each print, reducing the number of prints still required until there is no need to print any more. This is what the means by the base case being the simplest version of the problem. Recursion is used to simplify the problem with each function call.

The text continues with a math example, calculating the factorial of a positive integer. A factorial is calculated by multiplying an integer times the next smallest integer, then multiplying that times the next smallest integer, and so on until we multiply the most recent answer by one. The text shows us a way to state this in two rules, in which n represents the starting number:

If n = 0, then factorial(n) = 1
If n > 0, then factorial(n) = 1 * 2 * 3 * ... * n

This is not how I explained it above, but it will reach the same result whether we are counting up or counting down. This also satisfies our planning requirement: we have a base case and a recursive case. For example, cleaning up the typo in the online copy of the banana edition, the factorial of 6, which we will call factorial(6), can be computed as 1 * 2 * 3 * 4 * 5 * 6. (The online version has shows 3s in place of the asterisks. How odd...) To match my description, it can be computed as 6 * 5 * 4 * 3 * 2 * 1, except the "times one" step in either algorithm is not necessary.

The text then writes a function that will do this operation as a recursion:

def factorial(num):
   if num == 0:
      return 1
   else:
      return num * factorial(num - 1)

num = int(input("Enter a positive integer: "))
fact = factorial(num)

You don't have to believe it. Test it and you will see that it works. When a program, or function calls itself, that is formally called direct recursion. The text hints at a different kind of recursion, indirect recursion, which takes place when two or more functions make multiple calls to other functions to solve the same problem.

Examples of Recursion Algorithms

It may be hard to see problems that recursion will supply answers for, so the text gives us several examples to close out the chapter.

  • summing a range of values in a list (you could do anything with them, not just sum them)
  • creating a Fibonacci sequence, in which each new number is the sum of the previous two numbers
  • finding the greatest common divisor of two numbers
  • solving the Towers of Hanoi problem

As you might be thinking, unless you have a problem that lends itself to this kind of approach, it doesn't look like something we will go out of our way to use. The text reminds us that recursion is less efficient than looping when it comes to using computer resources. If a problem can be solved by either approach, and you are better with one than the other, the author's advice is to use the one you know better.

Assignments

Assignments for this chapter will be found in Blackboard. We will explore that in class.