Sum of First N Numbers Recursively
Summing numbers from $1$ to $N$ is a classic arithmetic operation. The sum of the first $N$ numbers can be calculated using recursion by formulating the problem as:
sum(N) = N + sum(N - 1)
The structure of the recursive function consists of:
- Base Case:
sum(0) = 0. When $N$ becomes $0$, the recursion stops and returns $0$. - Recursive Step:
n + sum(n-1). The function calls itself with $n-1$.
Trace of sum(3)
The step-by-step resolution of sum(3) is as follows:
sum(3)is called $\rightarrow$ callssum(2).sum(2)is called $\rightarrow$ callssum(1).sum(1)is called $\rightarrow$ callssum(0).sum(0)is called $\rightarrow$ base case matched, returns 0.sum(1)receives 0, computes $1 + 0 = 1$, returns 1.sum(2)receives 1, computes $2 + 1 = 3$, returns 3.sum(3)receives 3, computes $3 + 3 = 6$, returns 6.
Complexity Analysis
Time Complexity: O(N)
There are $N+1$ recursive calls, each executing in constant time $O(1)$.
Space Complexity: O(N)
At the deepest recursion level, there are $N+1$ stack frames concurrently on the Call Stack. Thus, auxiliary space is linear, $O(N)$.