Understanding space and time complexity - Part 2 (Recursive functions)

Let’s learn how to calculate s-t complexity of a recursive function.

 function sumOfNumbers(n) {
  if (n <= 0) {
    return 0;
  }
  return sumOfNumbers(n - 1) + n;
}

console.log(sumOfNumbers(4)); // 10:

What is Recursion?

First understand the logic of this function. We have sumOfNumbers which accepts an n as the argument and the same function is being returned with (n-1) as the argument with addition of n to it.

Recursion is simply calling the function in itself. Instead of using loops, we have a smart technique where we have a base case:

if (n <= 0) {
    return 0;
   }

When n<=0, the function will return 0. And this is crucial, without the base case, the function will run indefinite times.

Let’s take n as 4 in this case:

when n =4, sumOfNumbers will return sumOfNumbers(3) + 4
when n= 3, sumOfNumbers will return sumOfNumbers(2) + 3
when n= 2, sumOfNumbers will return sumOfNumbers(1) + 2
when n= 1, sumOfNumbers will return sumOfNumbers(0) + 1

and as soon as it goes to n=1, we know we have sumOfNumbers(0) which is 0.

So, let’s start putting these values back:

// unwinding these functions from reverse order
when n= 1, sumOfNumbers will return 0 + 1
when n= 2, sumOfNumbers will return 1 + 2
when n= 3, sumOfNumbers will return 3 + 3
when n =4, sumOfNumbers will return 6 + 4 = 10 <---- final answer

And if you look closely, this looks like a stack operation, i.e., LIFO, last-in-first-out.

Internally, all these function calls goes to a stack data structures. All function calls got stacked and as soon as it hits the base case, it started unwinding.

Stack Overflow

And if it doesn’t reach to the base case, and function calls got stacked on top of each other indefinitely, the compiler will throw the error, as it doesn’t have limited memory.

Errors in different languages:

Python ~1000 calls RecursionError: maximum recursion depth exceeded , JavaScript ~10,000–30,000 (depends on engine) RangeError: Maximum call stack size exceeded, C / C++ Depends on OS & compiler, typically 1–8 MB stack memory Segmentation fault / crash Java A few thousand calls StackOverflowError.

Space-Time Complexity

Now, we fully understand the flow of our program, its easier to calculate the time complexity.

As we checked, for n = 4 value, our function ran 5 times ( 4 + 1 (base-case)). So, time complexity is O(n).

For space complexity, we need to find how many times it got stacked because each call will take space in memory ( as discussed above, all function calls will be stored in the memory called stack).

for n = 4, it will be stored 4 + 1(base-case) times, hence O(n).

---