How Recursion Works with Call Stack and Its Big O Notation

Recursion is a function that defined itself by implementing repeated execution of statements, where a method invokes itself until the condition meets its baseline and recursion stops, like factorial calculation.

When designing Recursive Algorithms, you need to have two components: base case and recursion. The base case is where the recursive call stops when a certain condition is met. The recursion is when the condition of the base case is not met, the algorithm invokes itself recursively. Make sure the base case is always reached to avoid infinite recursion.

• Pros: DRY, Readability
• Cons: Large Stack (call stack structure)

Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack and follows a LIFO (Last-In-First-Out) approach. In recursion, the last function call needs to be completed first (reaches a return statement with the baseline that stops it from recalling itself), then it starts taking out the top elements from the stack if there is no return statement for the recursion function.

public static void reverse(DoublyLinkedList<Integer> intList) {
  if(!intList.isEmpty()) {
   int storedEle = intList.first();
   intList.removeFirst();
   reverse(intList);    // => recursive call
   intList.addLast(storedEle);    // unwinding storedEle
  }
 }

The call stack windup before the recursive call, then after the recursive call meets its baseline, the call stack unwinds down due to its call stack nature — where recursion happened and then something happened after the recursive call.

Initial list: size = 5, (10, 20, 30, 40, 50)
After reverse: (50, 40, 30, 20, 10)

Initial list: size = 6, (10, 20, 30, 40, 50, 60)
After reverse: (60, 50, 40, 30, 20, 10)

Photo by Андрей Сизов on Unsplash

Big O Analysis

Factorial

• O(n) -> invoke n+1 times while each takes O(1)
• input size — the value of n
• number of recursive call — n+1 — O(n)
• runtime for a single recursive call — O(1)

Search

• Search a sequence of n elements for a target element
• Total runtime = number of recursive calls * amount of time for one recursive call

Linear Search

• Examine each element while scanning the sequence
• Best case: one comparison, or O(1)
• Worst case: n comparisons, or O(n)
• On average: n/2 comparisons, or O(n)

Binary Search

• If the sequence is sorted, we can use a binary search
• Each time binary search is (recursively) invoked, the number of elements to be searched is reduced to at most half.
• Running time is O(log n)

Useful Resources

• https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation