Track the variable values of a recursive function using multiple pieces of paper to form a “stack” so that students can visualize what happens when a method calls itself and how each method call has its own unique variable values.

  • 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