Recursion

Introduction: 10.1.1

• Recursion is when a method calls itself
• Recursion which never ends is called infinite recursion

public void neverEnds() {
  System.out.println("This method will never end!");
}

Why use recursion?: 10.1.2

• Recursion is useful when solving problems where the structure of the problem repeats
  • If you wanted to know how much space a folder on your computer uses
    • You add up the size of all files in your folders, but folders have folders in them
• Recursion can be used to traverse a String, array, and ArrayList, like a loop
  • Any recursive solution can be written as a loop

Factorial method: 10.1.3

• A factorial is a good example of a recursive method
  • 4! is 4 * 3!; 3! is 3 * 2!; etc.
• To trace a recursive method, use a call stack
  • A stack to keep track of what methods were called, and what line they were called from
  • Where to return after a method exits
  • The main method is at the bottom of the call stack
• A recursive method usually has one condition where it returns a value instead of a recursive call
  • This is the base case
  • If a method doesn’t have this, it’s infinite recursion

public static int factorial(int val) {
  if (val == 0) {
    return 1;
  } else {
    return val * factorial(val - 1);
  }
}

Base Case: 10.1.4

• Every recursive method must have at least one base case to halt recursion
  • Usually an if statement to cause the recursion to stop by giving an answer instead of a recursive method call
  • The factorial of 0 returns 1 right away, because that is known

Tracing Recursive Methods: 10.1.5

• The call stack keeps track of the methods that you have called since the main method
  • A stack is a way of organizing data that adds and removes items only from the top of the stack
  • When you execute method a and it calls method b, the method call is placed in the stack along with where it is being called from
    • this tells the runtime where to return when the top of the stack finishes executing
    • When method b finishes executing, the runtime pops the method off the stack and returns execution to the next line to be executed in method a
  • When a method calls itself, a new method gets added to the top of the call stack
    • Execution pauses until the recursive call finishes
• One way to trace a call stack is to go bottom-up
  • Start with the beginning call and continue until you reach the base condition
  • This is useful for exams

whiteboard debugging ;)

Summary: 10.1.7

• A recursive method is ome which calls itself
• Recursive methods contain at least one base case
  • Halts recursion
• Recursive methods contain at least one recursive call
• Each recursive call has its own set of local variables, including formal parameters
• Parameter values capture the progress of a recursive process
• Any recursive solution can be replicated using iteration
• Writing recursive code is outside the scope of the AP Exam
• Recursion can be used to traverse a String, array, or ArrayList