Week 9 - Recursion

Lecture Notes: Recursive Methods

Recursive Void Methods

• Iterative vs. Recursive Methods:
  • Iterative methods use loops for repetition.
  • Recursive methods invoke themselves to solve smaller versions of the same problem.

public static void countdown(int n) {
    if (n == 0) {
        System.out.println("Blastoff!");
    } else {
        System.out.println(n);
        countdown(n - 1);
    }
}

• The method displays numbers from n to 0, then prints “Blastoff!”.

• Execution of Recursive Method:

  • Each invocation creates a new stack frame.
  • Frames are popped when base case is reached.

Recursive Stack Diagrams

• Stack Diagrams:

  • Represent the state of program during method invocation.
  • Base case frame is the last one.

• Example: Countdown Stack Diagram:

  • Imagine we call countdown(3);

main
  countdown (n=3)
    countdown (n=2)
      countdown (n=1)
        countdown (n=0)  // Base case, method returns
      countdown (n=1)  // This call returns the result (which is nothing)
    countdown (n=2)  // This call returns the result (which is nothing)
  countdown (n=3)  // This call returns the result (which is nothing)

• Example: nLines Stack Diagram:
  • Imagine we call nLines(3);

public static void nLines(int n) {
  if (n > 0) {
    nLines(n - 1);
    System.out.println();
  }
}

main
  nLines (n=3)
    nLines (n=2)
      nLines (n=1)
        nLines (n=0)  // Base case, method returns (nothing printed)
      nLines (n=1)  // This call returns (prints a newline)
    nLines (n=2)  // This call returns (prints a newline)
  nLines (n=3)  // This call returns (prints a newline)

1. main: The program starts in the main method.
2. nLines (n=3): The main method calls nLines with n=3.
3. nLines (n=2): The first recursive call to nLines occurs with n=2.
4. nLines (n=1): The method calls itself again with n=1.
5. nLines (n=0): The base case is reached (n <= 0), so the method returns without printing anything.
6. Returning: The calls start returning, each printing a newline as they return:
7. nLines(n=1) prints a newline.
8. nLines(n=2) prints a newline.
9. nLines(n=3) prints a newline.

Stack Overflow

• A stack overflow happens in computer programs that use recursion when a program tries to use more memory on the call stack than is available.

Info

Imagine a stack of plates at a restaurant. Each plate represents a method call. When a method is called, a new plate (frame) is added on top of the stack. This frame stores information about the method, like its parameters and local variables. In recursion, a method calls itself. This means a new plate gets added on top of the stack for each recursive call. If there are too many method calls (too many plates), the stack will run out of space, and you’ll get a stack overflow error. This is like trying to add too many plates to a real stack - they will all come crashing down!

• Stack Overflow Occurs if the base case is never reached, which causes infinite recursion.

Value-Returning Recursive Methods

public static long factorial(int n) {
  if (n == 0) {
    return 1; // Base case: factorial of 0 is 1
  } else {
    return n * factorial(n - 1); // Recursive case: n! = n * (n-1)!
  }
}

1. This method takes an integer n as a parameter.
2. The base case occurs when n is 0. In this scenario, the factorial of 0 is defined as 1, so the method returns 1.
3. If n is greater than 0, the recursive case applies. The method calculates n * factorial(n - 1). This breaks down the factorial of n into the product of n and the factorial of n - 1.
4. The recursive call factorial(n - 1) essentially calculates the factorial of a smaller version of the original problem (n - 1).
5. The result of the recursive call is then multiplied by n and returned as the factorial of the original n.

-warn

While this method is elegant and demonstrates recursion, it’s important to be aware that for larger values of n, this approach can lead to stack overflow errors. This is because each recursive call adds a new frame to the stack, and for very large factorials, the stack might not have enough memory to accommodate all the calls. For calculating factorials of larger numbers, an iterative approach is generally preferred.

Leap of Faith

• Assume recursive call works correctly.
• Similar to trusting built-in methods like Math.cos.

Counting Up Recursively

public static void countup(int n) {
    if (n == 0) {
        System.out.println("Blastoff!");
} else {
        countup(n - 1);
        System.out.println(n);
    }
}

Recursive Binary Method

public static void displayBinary(int value) {
    if (value > 0) {
        displayBinary(value / 2);
        System.out.print(value % 2);
    }
}

• Example: displayBinary Stack Diagram:
  • Imagine we call displayBinary(10);

main
  displayBinary (value = 10)
    displayBinary (value = 5)
      displayBinary (value = 2)
        displayBinary (value = 1)
          displayBinary (value = 0)  // Base case, method returns
        System.out.print(1 % 2)      // Prints "1"
      System.out.print(2 % 2)        // Prints "0"
    System.out.print(5 % 2)          // Prints "1"
  System.out.print(10 % 2)          // Prints "0"