Sum of First N Numbers
Easyn plus the sum of everything below
Problem
Return the sum 1 + 2 + ... + N using recursion.
Add n to the sum of the first n-1 numbers, bottoming out at 0.
The idea
sum(n) is n + sum(n-1), with sum(0) = 0. Trusting the recursive call to be correct for the smaller case is the mental move that makes recursion usable — you never need to unroll the whole thing in your head.
The trick
- Base case sum(0) = 0.
- The closed form n(n+1)/2 is O(1) — recursion here is for the lesson, not the speed.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n = 5 Values: 5.
1f(n):2 if n==0: return 03 return n + f(n-1)Input
- array
- [5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 5
- Output:
- 15
- Explanation:
- 1+2+3+4+5 = 15.
Example 2
- Input:
- n = 10
- Output:
- 55
- Explanation:
- 1+...+10 = 55.
Example 3
- Input:
- n = 1
- Output:
- 1
- Explanation:
- Just 1.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.