- Using a physical stack of papers as the stack help students visualize how the recursive function "pops off" the stack and returns a value to the previous function call.
- Activity Prep:
- Print out a simple recursive function, each student will need multiple copies of the function.
- Factorial is a good function to start with, using the code print each student 5 copies so they can trace through
factorial(5):
public int factorial(int n) {
// The value of n is: ____
if (n == 1) {
return 1;
}
// This line says: ____ * factorial(____)
return n * factorial(n - 1);
// factorial(n - 1) ended up returning the value ____
// This method will return the value ____
}
- Activity:
- Provide each student with five pieces of paper with the factorial function printed on it.
- Ask students to trace
factorial(5); - Have students trace through
factorial(5): - They begin by filling in the initial condition, "The value of n is 5."
- Each time the function calls itself students
- (a) mark where code execution was interrupted by the recursive call by drawing a line.
- (b) grab a new copy of the function to put "on the stack"
- Students place the recursive call on the stack by placing the new copy on top of the previous copy of the function.
- Students continue to trace through the code until a base case is reached.
- Once a base case is reached:
- Students "pop" the most recent method call off the stack by removing the top copy of the function and using its return value.
- Students should resume execution where they drew a line in the code.
- Students will continue to do this until they’ve successfully completed executing
factorial(5), filling in the value it returns. - Note: This activity can get confusing if using a recursive function that calls itself more than once (e.g.
fibonacci(n - 1) + fibonacci(n - 2)). - After using a simple recursive call, like factorial, you can have students advance to more complicated recursive functions.
- Numerical comma insertion method (turn 7000000 into 7,000,000) is a good segue between the simple factorial example and the more complicated Fibonacci example.
- Below are two different versions of recursive comma insertion methods you can use, simply add comments for students to fill in when they trace through them.
- Note that the
insertCommas()function includes several local variables for students to track as well as the argument that was passed in.
// Parameter is a String for this version.
public String insertCommas(String number) {
int size = number.length();
if (size < 4) {
return number;
} else {
String numberWithComma = "," + number.substring(size - 3, size);
String leftPartOfNumber =
Integer.toString(Integer.parseInt(number) / 1000);
return insertCommas(leftPartOfNumber) + numberWithComma;
}
}
// Parameter is an Int for this version
public String insertCommas(int number) {
if (n 1000) {
return number + "";
} else {
int last3 = n % 1000;
if (last3 10) { // need two zeroes
return insertCommas (n / 1000) + ",00" + last3;
} else if (last3 100) { // need one zero
return insertCommas (n / 1000) + ",0" + last3;
} else {
return insertCommas (n / 1000) + "," + last3;
}
}
}