Questions, Answers and Review
Introduction to Recursion
The Most Interesting Man in the World's About RecursionRecursion: when an algorithm is defined by referring to itself.
Recursion Example: Many Hands Make Light Work
Algorithm For Washing Dishes
Recursive Elements
Check Yourself
Implementing Recursive Functions
Implementation of Recursive Example
Check Yourself
Try It: Writing a Recursive Function (5m)
How Recursion Works
Function Call Stack
Call Stack for

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 itselflong 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 x^{y}
 But the recursive call is an easier task: x^{y  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
 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.
Tracing the Execution
 Remember the
power()
function from the last sectionlong 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 frommain()
: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; // prerecursion long result = power(x, y); // recursion result = result * x; // postrecursion 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
 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 ________.
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); 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 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) { 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
 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);
Exercise: Practicing Recursion
In this exercise we work through at several examples of recursion.
Specifications
 Determine who your pairprogramming partner is for this exercise.
 Work through each 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 as part of the next homework assignment.
Recursive Problems
 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 function using recursion named
printStars()
that receives a singleint
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, callingprintStars(8)
displays: ******** (8 asterisks). Save the sketch as printstars.  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?
 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 thelength()
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 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: from Wikipedia
 Recursion: from Harvard CS50.tv
 Understanding 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
Wrap Up and Reminders
 For the next homework, see the schedule
 When class is over, please shut down your computer.