Schedule‎ > ‎

### 13A: Recursion and Recursive Algorithms

• Questions from last class?

^ top

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

^ top

The Most Interesting Man in the World's
Secret Power: 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.

^ top

### 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 ``` `#include ` `using namespace std;` `void setup() {` `  Serial.begin(9600);` `}` `void loop() {` `  int count = 0;` `  cout << "\nEnter the number of dishes to wash: ";` `  cin >> count;` `  cout << count << endl;` ```  wash(count);   delay(1000); ````}` `void wash(int counter) {` `  if (counter == 0) { // base case` `    cout << "Done washing dishes" << endl;` `    return;` `  } else {` `    cout << "Washing one dish; number remaining: ";` `    counter = counter - 1; // solve part of problem` `    cout << counter << endl;` `    wash(counter); // recursive call` `    cout << "Washed " << (counter + 1) << " dishes so far." << endl;` `  }` `}`

Click here for:  An Introduction to Recursion  You will need to be able to write a Factorial recursive function.  This video shows you how to do it.

#### 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.
```#include <ArduinoSTL.h>using namespace std;void setup() {  Serial.begin(9600);}void loop() {  int count = 0;  cout << "How high to count? ";  cin >> count;  cout << count << endl;  // call recursive function here}
```
2. Add a stub for a `void` function named `recursiveCounter` that has a single `int` parameter named `counter`.
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 `counter` 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.

^ top

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

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

^ top

### Pre- and Post-Recursion

• Remember the structure of the recursive case in our dish washing example
```    cout << "Washing one dish; number remaining: ";    counter = counter - 1; // solve part of problem    cout << counter << endl;    wash(counter); // recursive call    cout << "Washed " << (counter + 1) << " dishes so far." << endl;
```
• Before the recursive call is a `cout` statement showing the number of dishes to wash
```    cout << "Washing one dish; number remaining: ";    counter = counter - 1; // solve part of problem    cout << counter << endl;
```
• Then comes the recursive call:
```wash(counter); // recursive call
```
• After the recursive call another `cout` is executed
```cout << "Washed " << (counter + 1) << " dishes so far." << endl;
```
• 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 `counter = counter - 1;` is made before the recursion (pre-recursion)
• Printing the number of dishes washed is made after the recursion (post-recursion)
```cout << "Washed " << (counter + 1) << " dishes so far." << endl;
```

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

2. After the recursive call, add a print statement to display the value of count, like:
```cout << "After the recursive call counter is " << counter << endl;
```
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 counter) {
if (0 > counter) {
return;
}
cout << "pre-recursion counter is " << counter << endl;
recursiveCounter(counter - 1);
cout << "post-recursion counter is " << counter << endl;;
}
```
4. In the above recursive code, the post-recursion statement is ________.

^ top

### 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 2y

1. For this activity we will calculate 2y using the power of student brains.
2. You will be asked for the answer to 2y, where y is a positive integer value.
3. If the value of y is zero then say the answer.

For example, say: "20 is 1."

4. Otherwise, ask the student next to you for the value of 2y - 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 ________.

^ top

### Exercise 1:  Coding the Exponentiation Algorithm (power.ino)

#### Use this Starter Code.  Fill in the implementation of the recursive power function.

 ```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 ``` ```#include using namespace std;void setup() { Serial.begin(9600);}void loop() { int x = 0; int y = 0; cout << "\nCalculating power(x, y)" << endl; cout << "Enter x: "; cin >> x; cout << x; cout << " Enter y: "; cin >> y; cout << y << endl; long p = power(x, y); cout << "power(" << x << ", " << y << ") = " << p << endl;}long power(long x, long y) { if (y == 0) { //ENTER YOUR BASE CASE CODE HERE } else { y = y - 1; //ENTER YOUR RECURSIVE CASE CODE HERE }} ```

Submit your power.ino code to Canvas.

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

^ top

### 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() { int x = 0; int y = 0; cout << "\nCalculating power(x, y)" << endl; cout << "Enter x: "; cin >> x; cout << x << endl; cout << "Enter y: "; cin >> y; cout << y << endl; long p = power(x, y); cout << "power(" << x << ", " << y << ") = " << p << endl;}long power(long x, long y) { if (y == 0) { cout << "power(" << x << ", " << y << ") returns 1 (base case)" << endl; return 1; } else { cout << "power(" << x << ", " << y << ") calls power(" << x << ", " << (y - 1) << ")" << endl; y = y - 1; long result = power(x, y); //recursion result = result * x; //post-recursion cout << "power(" << x << ", " << (y + 1) << ") = returns " << result << endl; return result; }} ```

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

^ top

### 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); cout << "Square Root Calculator";}void loop() { double x = readPosNum("\nEnter a positive number: "); cout << "Enter a positive number: "; cout << "sqrt(" << x << ") = " << sqrt(x) << endl;}double readPosNum(String prompt) { double input = -1; do { Serial.print(prompt); cin >> input; cout << input << endl; if (input <= 0) { cout << "Error: number must be > 0" << endl; } } 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) {  double input = -1;  Serial.print(prompt);  cin >> input;  cout << input << endl;  if (input <= 0) {    cout << "Error: number must be > 0" << endl;    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 ``` ```#include using namespace std;void setup() { Serial.begin(9600); Serial.println("Square Root Calculator");}void loop() { double x = readPosNum("\nEnter a positive number: "); cout << "Enter a positive number: "; cout << "sqrt(" << x << ") = " << sqrt(x) << endl;}double readPosNum(String prompt) { double input = -1; Serial.print(prompt); cin >> input; cout << input << endl; if (input <= 0) { cout << "Error: number must be > 0" << endl; return readPosNum(prompt); // recursion } return input;} ```

### When to use Recursion vs. Loops

In simple cases like what we have covered here,  it doesn't make much difference if you use recursion or loops.  However,  there are a number of ways that data is stored efficiently (tree structures for example - learned about in a more advanced class) where being able to write a recursive function is much simpler and more natural.

#### 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);
```

^ top

### Exercise 2: Practicing Recursion (20m)

4 files @ 3 pts each = 12 pts total

In this exercise you will work through at least 4 examples of recursion (your choice out of the 6):

#### Specifications

1. Determine who your pair-programming partner is for this exercise.
2. Work through four 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 to canvas.

#### Recursive Problems

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

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

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?

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

#### Recursion Humor

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