CompSci notes (Fri April 10th)

Recursive Algorithms

• Base Case: Every recursive algorithm must have a base case to avoid stack overflow or infinite recursion.

• Simplification: Each recursive call should simplify the problem, approaching the base case.

Method Call Behavior

• When a method is called, the current method pauses execution until the called method completes.

• Each method call creates a new copy with its own local variables (activation record) on the stack.

Stack Management

• The execution stack is a Last In, First Out (LIFO) structure managing method calls and returns.

• Stack overflow occurs when too many methods are called without returning to the base case, exhausting memory.

Example Recursive Methods

• Right Vertical Method: Prints digits of a number vertically by recursively dividing the number by 10 until reaching a base case (single digit), then prints each digit from the last call to the first.

  • Base Case: When number < 10.

• Fibonacci Sequence: Corrected method should call fib(n-1) + fib(n-2) to retrieve Fibonacci numbers, adding necessary base cases:

  • Base Cases: fib(0) = 0 and fib(1) = 1.

Common Mistakes in Recursion

• Missing base case can lead to infinite recursion and stack overflow.

• Recursive calls must lead towards the base case, not away from it.