Sum of Natural Numbers using Recursion

Computing the sum of the first N positive integers (natural numbers) is a classic algorithmic problem.

The sum can be expressed mathematically as:

Sum(N) = N + (N - 1) + (N - 2) + ... + 1

With the base case:

Sum(0) = 0

Recursive Formula

To solve this recursively, we notice that the sum of first N numbers is simply N added to the sum of the first N - 1 numbers.

Base Case

If N <= 0, Sum(N) = 0

Recursive Case

If N > 0, Sum(N) = N + Sum(N - 1)

For example, to calculate Sum(4):

Sum(4) = 4 + Sum(3)
Sum(3) = 3 + Sum(2)
Sum(2) = 2 + Sum(1)
Sum(1) = 1 + Sum(0)
Sum(0) = 0 (Base case reached)

Now, we propagate the return values back up:

Sum(1) = 1 + 0 = 1
Sum(2) = 2 + 1 = 3
Sum(3) = 3 + 3 = 6
Sum(4) = 4 + 6 = 10

The Call Stack Flow

When a function is called, the system pushes its arguments, local variables, and return address onto the Call Stack as a Stack Frame. Since each recursive call suspends the parent call, we stack these frames vertically:

sum(4) is called (pushes to stack, suspended)
sum(3) is called (pushes to stack, suspended)
sum(2) is called (pushes to stack, suspended)
sum(1) is called (pushes to stack, suspended)
sum(0) is called (pushes to stack, hits Base Case)

At the base case, the stack reaches its maximum winding depth. Then, during the unwinding phase, the values are computed and returned one-by-one, popping frames off the stack until the original call sum(4) resolves to 10.

Complexity Analysis

Time Complexity: O(N) because the function makes exactly N + 1 calls, with each call executing in constant time O(1).
Space Complexity: O(N) due to the recursive stack depth. The maximum height of the Call Stack at any point is N + 1 stack frames.