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.

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

  • 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 a sequence of n elements for a target element
  • Total runtime = number of recursive calls * amount of time for one recursive call
  • 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)
  • 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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Hanwen Zhang

Full-Stack Software Engineer at a Healthcare Tech Company | Document My Coding Journey | Improve My Knowledge | Share Coding Concepts in a Simple Way