Recursion 2

From Huben's Wiki
Jump to: navigation, search

Review Handout 2.

Java keeps track of which methods are running and have called each other on the stack. When there is a run-time error in a program, Dr. Java shows you the stack: the list of which methods called which other methods. When you call a method, it is put on top of the stack, when it is finished, it pops off the stack. You program puts main() on the stack when it starts, and then when main() calls another method, that method is put on the stack too.

Handout 3: Tracing Recursion

  • Read the first page of the handout to see their stack notation.
  • You can run this code in Dr. Java to see how factorial calls itself and returns values to itself.
public class ShowRecursion
{
  public static void main(String[] args)
  {
    int result = factorial(5, 1);
  }
  
  public static int factorial(int n, int stackLevel)
  {
    System.out.print("Entering Stack Level: " + stackLevel + ".  Call to factorial(" + n + ");  ");
    if (n <= 1)
    {
      System.out.println("End condition, can stop recursing now, returning 1");
      return 1;
    }
    System.out.println("Recursing with factorial(" + (n - 1) +") now");
    int result = factorial(n - 1, stackLevel + 1);
    System.out.print("Resuming Stack Level: " + stackLevel + ".  Result received from factorial(" + (n - 1) +"): " + result);
    System.out.println("  Multiplying result by " + n + " and returning " + n * result);
    return n * result;
  }
}

Return to Handout 3:

  • Do the first 3.
  • Build the call stack upwards, then bring the returns downwards
Personal tools
translate