Questions, Answers and Review
 Questions from last class?
 Questions about homework?
^ 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
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:
 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 easytosolve 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
 True or false: a recursive step needs to solve some part of a problem.
 The easytosolve part of a recursion is know as the ________ case.
 True or false: every recursive algorithm must have a base case.
^ top
Implementing Recursive Functions
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 <ArduinoSTL.h>
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
 True or false: Recursion is a form of looping but without using a loop statement.
 Recursion is implemented in C++ using ifstatements and ________.
 In recursive algorithms, an ifstatement is needed to test for the ________ case.
Try It: Writing a Recursive Function (5m)
 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 }
 Add a stub for a
void function named recursiveCounter that has a single int parameter named counter .
 Within
loop() , add code to call the recursiveCounter() function like:
recursiveCounter(count);
 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.
 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
 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)
Check Yourself
 Items are placed on the top of a stack and removed from the ________.
 True or false: the first item placed on a stack is the last item removed.
 Functions are tracked on a call stack with a stack frame or ________.
 True or false: a function on a call stack is active and has yet to complete execution.
More information
^ top
Pre and PostRecursion
 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 prerecursion
 Code executed after the recursive call is known as post recursion
 The calculation
counter = counter  1; is made before the recursion (prerecursion)
 Printing the number of dishes washed is made after the recursion (postrecursion)
cout << "Washed " << (counter + 1) << " dishes so far." << endl;
Some Recursion Terminology
Try It: Exploring Pre and PostRecursion (3m)
 Start with your code from the last Try It: Writing a Recursive Function.
 After the recursive call, add a print statement to display the value of count, like:
cout << "After the recursive call counter is " << counter << endl;
 Be prepared to answer the following Check Yourself questions when called upon.
Check Yourself
 True or false: within the recursive step, code executed before the recursive call is known as prerecursion.
 Within the recursive step, code executed after the recursive call is known as ________ recursion.
 In the following recursive code, the prerecursion calculation is ________.
void recursiveCounter(int counter) {
if (0 > counter) {
return;
}
cout << "prerecursion counter is " << counter << endl;
recursiveCounter(counter  1);
cout << "postrecursion counter is " << counter << endl;;
}
 In the above recursive code, the postrecursion statement is ________.
^ top
Developing a Recursive 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 x^{y  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 x^{0}, which is 1
 Else (while y ≥ 1):
 Ask someone else to compute x^{y  1}
 We multiply the result of x^{y  1} times x
Activity: Calculating 2^{y}
 For this activity we will calculate 2^{y} using the power of student brains.
 You will be asked for the answer to 2^{y}, where y is a positive integer value.
 If the value of y is zero then say the answer.
For example, say: "2^{0} is 1."
 Otherwise, ask the student next to you for the value of 2^{y  1}
For example, if you were asked for 2^{14} , ask the student next to you: "What is 2^{13}?"
 When you get an answer to your question, double it and say the answer out loud.
For example, if you get an answer to 2^{13}, say: "2^{14} is 16,384."
Check Yourself
 True or false: exponentiation with positive integers corresponds to repeated multiplication.
 The following is known as a ________ relation.
x^{y} = x * x^{y  1}
 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 <ArduinoSTL.h> 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
Termination: I Won't be Back
Check Yourself
 When a recursive function calls itself, that step known as the ________ step.
 True or false: the base case always includes a recursive function call.
 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; //postrecursion cout << "power(" << x << ", " << (y + 1) << ") = returns " << result << endl; return result; } }

Check Yourself
 In the following recursive code, the prerecursion calculation is ________.
long power(long x, long y) {
if (y == 0) {
return 1;
} else {
long result = power(x, y  1);
return x * result;
}
}
 In the above recursive code, the postrecursion 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 dowhile 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 reenter 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 <ArduinoSTL.h> 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. LoopsIn 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
 True or false: recursion is a way of looping without using a loop statement.
 True or false: Recursion can simplify code such as input validation.
 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
 Determine who your pairprogramming partner is for this exercise.
 Work through four of the following recursive problems in order with two people working on one computer.
 Alternate the driver and navigator for each problem.
 Start by writing or typing the recursive algorithm and then implement the code.
 Make sure you discuss the solutions with your partner as you develop them together.
 Save your solutions using the specified names and turn in the
ino files to canvas.
Recursive Problems
 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.  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.
 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.
 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.
 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.
 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?
Exercise 2: Extra Credit: turn in all 6 problems above (add 2 problems = 6 pts additional)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 prerecursion
 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:
Source: http://boingboing.net/2011/11/16/hulkhoganrecurssion.html
^ top
Wrap Up and Reminders
 For the next homework, see the schedule
 When class is over, please shut down your computer.
 Complete unfinished exercises from today before the next class meeting
^ top
