Home‎ > ‎CS 11M‎ > ‎

Recursion and Recursive Algorithms

Questions, Answers and Review

  • Questions from last class?
  • Questions about homework?

Introduction to Recursion

Learner Outcomes

At the end of the lesson the student will be able to:

  • Design recursive algorithms
  • Code recursive functions
  • Trace the processing steps of recursive functions
Recursion is interesting

The Most Interesting Man in the World's
Secret Power: Recursion

About Recursion

Recursion: when an algorithm is defined by referring to itself.

  • Recursion is a natural approach to some problems
  • It allows us to break down a problem into one or more subproblems similar in form to the original problem
    • Sounds circular, but in practice is not
  • Recursion divides the problem into two parts:
    • Recursive step
    • Base case
  • The recursive step solves part of the problem and then calls the same function
  • Since the recursive step solves part of the problem, it passes a smaller problem to the recursive function
  • Eventually the smaller problem becomes easy enough to just solve
  • The easy-to-solve problem is known as the base case

Recursion Example: Many Hands Make Light Work

  • What if we were asked to do some repetitive task like washing the dishes?
  • We look at the pile of dishes and realize we have better things to do
  • So we wash one dish and then ask someone else to wash the dishes
    • Then you leave as soon as possible
  • The next person notices your actions and decides to do the same
  • They wash one dish and then ask someone else to wash the dishes
  • This sequence repeats until all the dishes are washed and the sink is empty
  • Writing this as an algorithm, we have:

Algorithm For Washing Dishes

  • If the sink is empty, do nothing
  • Else:
    • Wash one dish
    • Ask someone else to wash the dishes

Recursive Elements

  • Notice the recursive nature of the algorithm
  • The "else" clause calls itself:
    • To do the dishes, we ask someone else to do the dishes
  • To make sure this algorithm is not an endless passing of the buck, each person does some work
  • This makes the job passed to the next person smaller
  • When all the dishes are done, the chain of asking someone else to do the dishes is broken

Check Yourself

  1. True or false: a recursive step needs to solve some part of a problem.
  2. The easy-to-solve part of a recursion is know as the ________ case.
  3. True or false: every recursive algorithm must have a base case.

Implementing Recursive Functions

  • Now that we see how recursion works, let us look at how to implement it in a program
  • We implement recursion in C++ using functions
  • Each function contains a conditional statement
  • One of the statements contains a call the same function
  • This structure is shown below:
    returnType recursiveFunction(parameters) {
        if (stopping condition) { // base case
            // Problem is very easy
            // so solve it and return
        } else { // recursive step
            // Solve part of the problem
            // leaving a smaller problem
            recursiveFunction(arguments);
        }
    }
    
  • Like a loop, a recursive function must have some way to end
  • We often write the base case first and the recursive step second
  • The code below implements our recursive example

Implementation of Recursive Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void setup() {
  Serial.begin(9600);
  Serial.setTimeout(-1);
}

void loop() {
  int count = readInt("\nEnter the number of dishes to wash: ");
  wash(count);
}

void wash(int count) {
  if (count == 0) { // base case
    Serial.println("Done washing dishes");
    return;
  } else {
    Serial.print("Washing one dish; number remaining: ");
    count = count - 1; // solve part of problem
    Serial.println(count);
    wash(count); // recursive call
    String str = "Washed ";
    Serial.println(str + (count + 1) + " dishes so far.");
  }
}

int readInt(String prompt) {
  Serial.print(prompt);
  while (!Serial.available());
  int x = Serial.parseFloat();
  Serial.println(x);
  return x;
}

Check Yourself

  1. True or false: Recursion is a form of looping but without using a loop statement.
  2. Recursion is implemented in C++ using if-statements and ________.
  3. In recursive algorithms, an if-statement is needed to test for the ________ case.

Try It: Writing a Recursive Function (5m)

  1. Copy the following program into a text editor, save it as recursion.ino, and then compile and run the starter program to make sure you copied it correctly.
    void setup() {
      Serial.begin(9600);
      Serial.setTimeout(-1);
    }
    
    void loop() {
      Serial.println("How high to count?");
      int count = Serial.parseFloat();
      // call recursive function here
    }
    
  2. Add a stub for a void function named recursiveCounter that has a single int parameter named count.
  3. Within loop(), add code to call the recursiveCounter() function like:
    recursiveCounter(count);
    
  4. In the recursiveCounter() function, add code to print the numbers from count to 0 recursively. Do NOT use a loop statement.

    Hint: Look at the code for the washing dishes example.

  5. Check to see if the student on either side of you needs help. If so, offer to help them.

How Recursion Works

  • To understand how recursion works, we must consider a data structure known as a stack
  • A stack is like a pile of dishes: Stack of dishes
  • When a dish is placed on the stack, it is placed on top
  • Similarly, when a dish is removed from the stack, it is taken from the top
  • The last dish put on the stack is the first dish removed from the stack:
    • Otherwise you get a lot of broken dishes

Function Call Stack

  • When a program calls a function, it must know how to return to its caller
  • To make this possible, it pushes all the information it needs to remember onto a stack
    • Return address
    • Local variables and parameters
  • This stack is known as the function call stack
  • The information saved is known as the stack frame or activation record
  • Every function call creates a new stack frame
  • Every time a function returns, the stack frame data is popped off the stack

Call Stack for wash(3)

Call Stack for wash

Check Yourself

  1. Items are placed on the top of a stack and removed from the ________.
  2. True or false: the first item placed on a stack is the last item removed.
  3. Functions are tracked on a call stack with a stack frame or ________.
  4. True or false: a function on a call stack is active and has yet to complete execution.

More information

Pre- and Post-Recursion

  • Remember the structure of the recursive case in our dish washing example
    Serial.print("Washing one dish; number remaining: ");
    count = count - 1; // solve part of problem
    Serial.println(count);
    wash(count); // recursive call
    String str = "Washed ";
    Serial.println(str + (count + 1) + " dishes so far.");
    
  • Before the recursive call is a cout statement showing the number of dishes to wash
    Serial.print("Washing one dish; number remaining: ");
    count = count - 1; // solve part of problem
    Serial.println(count);
    
  • Then comes the recursive call:
    wash(count); // recursive call
    
  • After the recursive call another cout is executed
    String str = "Washed ";
    Serial.println(str + (count + 1) + " dishes so far.");
    
  • Within the recursive case, code executed before the recursive call is known as pre-recursion
  • Code executed after the recursive call is known as post recursion
  • The calculation count = count - 1; is made before the recursion (pre-recursion)
  • Printing the number of dishes washed is made after the recursion (post-recursion)
    String str = "Washed ";
    Serial.println(str + (count + 1) + " dishes so far.");
    

Some Recursion Terminology

Some commonly used recursion terms

Try It: Exploring Pre- and Post-Recursion (3m)

  1. Start with your code from the last Try It: Writing a Recursive Function.
  2. After the recursive call, add a print statement to display the value of count, like:
    Serial.println(count); // post-recursion
    
  3. Be prepared to answer the following Check Yourself questions when called upon.

Check Yourself

  1. True or false: within the recursive step, code executed before the recursive call is known as pre-recursion.
  2. Within the recursive step, code executed after the recursive call is known as ________ recursion.
  3. In the following recursive code, the pre-recursion calculation is ________.
    void recursiveCounter(int count) {
      if (0 > count) {
        return;
      }
      Serial.println(count);
      recursiveCounter(count - 1);
      Serial.println(count);
    }
    
  4. In the above recursive code, the post-recursion statement is ________.

Developing a Recursive Algorithm

  • Before we write recursive functions, we must develop a recursive algorithm
  • To develop a recursive algorithm, we must find a way to do the following:
    1. Use a solution to a smaller or easier version of a problem to arrive at the solution itself
    2. Know when the problem is small enough to solve directly
  • As another example of recursion, let us look at exponentiation
  • We will limit ourselves to positive integers
  • The mathematical notation for exponentiation is:

    xy

  • A function prototype for exponentiation could be:
    int power(int x, int y);
    
  • The definition of exponentiation when y is a positive integer is:

    xy = 1 * x * x * x ... (y times)

  • As we can see, the operation corresponds to repeated multiplication
  • Another way to express the operation is as a recurrence relation

    xy = x * xy - 1

  • The recurrence relation shows the recursive step we need for our algorithm

Thinking Recursively

  • We start developing the algorithm by working through the process by hand
  • It seems like a lot of work, and so we consider how to get someone else to do most of the work
  • If we could get someone else to calculate xy - 1, we could just multiply by x one time
  • This process could repeat until we are done
  • How would we know when we were done?

Recursive Algorithm For Exponentiation

  • If y is 0, we are done and the result is x0, which is 1
  • Else (while y ≥ 1):
    • Ask someone else to compute xy - 1
    • We multiply the result of xy - 1 times x

Activity: Calculating 2x

  1. For this activity we will calculate 2x using the power of student brains.
  2. You will be asked for the answer to 2x, where x is an integer value.
  3. If the value of x is one or less then say the answer.

    For example, say: "21 is 2."

  4. Otherwise, ask the student next to you for the value of 2x - 1

    For example, if you were asked for 214 , ask the student next to you: "What is 213?"

  5. When you get an answer to your question, double it and say the answer out loud.

    For example, if you get an answer to 213, say: "214 is 16,384."

Check Yourself

  1. True or false: exponentiation with positive integers corresponds to repeated multiplication.
  2. The following is known as a ________ relation.

    xy = x * xy - 1

  3. The base case of our recursive algorithm occurs when y is equal to ________.

Coding the Recursive Algorithm

  • Implementing a recursive algorithm is usually straightforward

Example Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void setup() {
  Serial.begin(9600);
  Serial.setTimeout(-1);
}

void loop() {
  Serial.println("\nCalculating power(x, y)");
  int x = readInt("Enter x: ");
  int y = readInt("Enter y: ");
  long p = power(x, y);
  String str = "power(";
  Serial.println(str + x + ", " + y + ") = " + p);
}

long power(long x, long y) {
  if (y == 0) {
    return 1;
  } else {
    y = y - 1;
    long result = power(x, y);
    result = result * x;
    return result;
  }
}

int readInt(String prompt) {
  Serial.print(prompt);
  while (!Serial.available());
  int x = Serial.parseFloat();
  Serial.println(x);
  return x;
}

The Recursive Call

  • Note how the power() function calls itself
    long power(long x, long y) {
        ...
            y = y - 1;
            long result = power(x, y);
            result = result * x;
        ...
    }
    
  • Calling a function from within that function is a recursive call
  • The arguments to the recursive call must define a task that is easier, smaller or closer to completion than the original task
  • In this case, the caller must calculate xy
  • But the recursive call is an easier task: xy - 1

Termination: I Won't be Back

  • The power() function has a conditional return that does not involve a recursive call:
    long power(long x, long y) {
        if (y == 0) {
            return 1;
        ...
        }
    }
    
  • The termination step is essential to any recursive procedure
  • It checks to see if the task can be carried out without using recursion
  • If so, it terminates the recursion by preventing any further recursive calls
  • Note that the terminating condition must be checked before a recursive call
  • Otherwise, the recursive call would go on indefinitely
    • The terminating condition would never be reached

Check Yourself

  1. When a recursive function calls itself, that step known as the ________ step.
  2. True or false: the base case always includes a recursive function call.
  3. True or false: the recursive step must always define a task that is easier, smaller or closer to completion than the original task.

Tracing the Execution

  • Remember the power() function from the last section
    long power(long x, long y) {
        if (y == 0) {
            return 1;
        } else {
        y = y - 1;
            int result = power(x, y);
            result = result * x;
            return result;
        }
    }
    
  • To see how a recursive function works, we can add print statement to trace the flow
  • As an example, we trace power(2, 3) called from main():
    main() calls power(2, 3)
      power(2, 3) calls power(2, 2)
        power(2, 2) calls power(2, 1)
          power(2, 1) calls power(2, 0)
            power(2, 0) returns 1 (base case)
          power(2, 1) returns 2
        power(2, 2) returns 4
      power(2, 3) returns 8
    power(2, 3) returns 8 to main()
    
  • Note that the first half of the trace makes successive function calls
    • Until the base case is reached
  • The second half returns the values from the recursive calls

Instrumented Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void setup() {
  Serial.begin(9600);
  Serial.setTimeout(-1);
}

void loop() {
  Serial.println("\nCalculating power(x, y)");
  int x = readInt("Enter x: ");
  int y = readInt("Enter y: ");
  long p = power(x, y);
  String str = "power(";
  Serial.println(str + x + ", " + y + ") = " + p);
}

long power(long x, long y) {
  String str = "power(";
  if (y == 0) {
    Serial.println(str + x + ", " + y + ") returns 1 (base case)");
    return 1;
  } else {
    Serial.println(str + x + ", " + y + ") calls power(" 
      + x + ", " + (y - 1) + ")");
    y = y - 1; // pre-recursion
    long result = power(x, y); // recursion
    result = result * x; // post-recursion
    Serial.println(str + x + ", " + (y + 1) + ") returns " + result);
    return result;
  }
}

int readInt(String prompt) {
  Serial.print(prompt);
  while (!Serial.available());
  int x = Serial.parseFloat();
  Serial.println(x);
  return x;
}

Check Yourself

  1. In the following recursive code, the pre-recursion calculation is ________.
    long power(long x, long y) {
        if (y == 0) {
            return 1;
        } else {
            long result = power(x, y - 1);
            return x * result;
        }
    }
    
  2. In the above recursive code, the post-recursion calculation is ________.

Using Recursion with Input Validation

  • Let us apply recursion to the problem of input validation, which we discussed in lesson 07B
  • We start with defining a sketch to calculate square roots as shown below

Input Validation with do-while Loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void setup() {
  Serial.begin(9600);
  Serial.setTimeout(-1);
  Serial.println("Square Root Calculator");
}

void loop() {
  double x = readPosNum("\nEnter a positive number: ");
  String str = "sqrt(";
  Serial.println(str + x + ") = " + sqrt(x));
}

double readPosNum(String prompt) {
  double input = -1;
  do {
    Serial.print(prompt);
    while (!Serial.available());
    input = Serial.parseFloat();
    Serial.println(input);
    if (input <= 0) {
      Serial.println("Error: number must be > 0");
    }
  } while (input <= 0);
  return input;
}
  • In the readPosNum() function we verify that the input is a positive number
  • If the input is not positive, we use a loop to make the user re-enter the number
    do {
    // ... input code here
    } while (input  <= 0);
    
  • In addition, we use an if-statement to detect an error and print an error message
  • The loop complicates the code
  • We can simplify the code by using recursion instead:
    double readPosNum(String prompt) {
      Serial.print(prompt);
      while (!Serial.available());
      double input = Serial.parseFloat();
      Serial.println(input);
      if (input <= 0) {
        Serial.println("Error: number must be > 0");
        return readPosNum(prompt); // recursion
      }
      return input;
    }
    
  • Notice how much shorter and simpler the code looks
  • The loop is replaced by a function call and the variable can be declared when used
  • All we needed to repeat the input operation when an error occurs was one line:
    return readPosNum(prompt);
    

Example of Input Validation with Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void setup() {
  Serial.begin(9600);
  Serial.setTimeout(-1);
  Serial.println("Square Root Calculator");
}

void loop() {
  double x = readPosNum("\nEnter a positive number: ");
  String str = "sqrt(";
  Serial.println(str + x + ") = " + sqrt(x));
}

double readPosNum(String prompt) {
  Serial.print(prompt);
  while (!Serial.available());
  double input = Serial.parseFloat();
  Serial.println(input);
  if (input <= 0) {
    Serial.println("Error: number must be > 0");
    return readPosNum(prompt); // recursion
  }
  return input;
}

Check Yourself

  1. True or false: recursion is a way of looping without using a loop statement.
  2. True or false: Recursion can simplify code such as input validation.
  3. True or false: the value returned in the following line is the value the user enters that passes the validation tests.
    return readPosNum(prompt);
    

Exercise: Practicing Recursion

In this exercise we work through at several examples of recursion.

Specifications

  1. Determine who your pair-programming partner is for this exercise.
  2. Work through each of the following recursive problems in order with two people working on one computer.
  3. Alternate the driver and navigator for each problem.
  4. Start by writing or typing the recursive algorithm and then implement the code.
  5. Make sure you discuss the solutions with your partner as you develop them together.
  6. Save your solutions using the specified names and turn in the ino files as part of the next homework assignment.

Recursive Problems

  1. Write a function using recursion to print numbers from 0 to n, saving the sketch as countup.

    Hint: Look at the code for the washing dishes example.

  2. Write a function using recursion to print numbers from n to 0, saving the sketch as countdown.

    Hint: Remember the discussion of pre- and post recursion. You only need to move the output statement of the previous problem to solve this one.

  3. Write a function using recursion named printStars() that receives a single int parameter and returns nothing. It the parameter value is greater than zero, the function prints to the Serial Monitor the given number of asterisks; otherwise it does nothing. For instance, calling printStars(8) displays: ******** (8 asterisks). Save the sketch as printstars.
  4. Write a recursive function for computing a factorial for n, denoted mathematically by n!, where n! is the product of all positive integers less than or equal to n, saving the sketch as factorial.

    Examples of factorials:

    factorial(0) = 1 (by definition)
    factorial(1) = 1
    factorial(2) = 2 * 1 = 2
    factorial(3) = 3 * 2 * 1 = 6
    factorial(4) = 4 * 3 * 2 * 1 = 24
    

    Hint: The function needs to return a number. if you are stuck, see the Harvard CS50.tv movie.

  5. Write a recursive function for summing the values between 1 and n, where n is any positive integer, saving the sketch as summing.

    Examples of summing:

    sum(1) = 1
    sum(2) = 2 + 1 = 3
    sum(3) = 3 + 2 + 1 = 6
    sum(4) = 4 + 3 + 2 + 1 = 10
    

    Hint: The function needs two parameters and returns a number.

  6. We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears for all the bunnies recursively without loops or multiplication or division. Save the sketch as bunnyears.

    Example results of calling the bunnyEars() function:

    bunnyEars(0) -> 0
    bunnyEars(1) -> 2
    bunnyEars(2) -> 4
    bunnyEars(3) -> 6
    

    Hint: The bunnyEars() function needs to return the number of bunny ears. If you know the number of ears for n - 1 bunnies, how many more ears on n bunnies?

  7. Write a function using recursion that displays a string in reverse. Do not use arrays, loops or additional strings. Save the sketch as reverse.

    Hints: Recall that you can access part of a string using the substring() function. Also, you can determine the length of a string using the length() function. In addition, you can use square bracket notation to access a single character. Furthermore, your recursive function will need two parameters: one for the string and one for the index of the string.

Summary

  • Recursion is when an algorithm is defined in terms of itself
  • It allows us to define subproblems similar in form to the original
  • Recursion always has two parts:
    • Base case
    • A problem that is closer to the solution
  • Eventually, the base case is always called
  • Without the base case, we would have infinite recursion
  • Code executed before the cursive call is known as pre-recursion
  • Code executed after the call is known as post recursion
  • Recursion makes some code shorter and easier to understand, such as input validation

More Information on Recursion

Recursion Humor

  • If you still don't get it, See: "Recursion".
  • "To understand recursion, you must first understand recursion." ~unknown
  • Search Google about recursion
  • The volume of a pizza of thickness a and radius z is ________.
  • The value of 190 (be) in hexadecimal is ________.
  • Hulk Hogan displayed recursively: Recursive Hulk Hogan

    Source: http://boingboing.net/2011/11/16/hulk-hogan-recurssion.html

Wrap Up and Reminders

  • For the next homework, see the schedule
  • When class is over, please shut down your computer.
Comments