Skip to main content

Sum of N natural numbers

Recursive Thinking​

How am I thinking to solve this problem? Okay, I need to find:

sum(n) = 1 + 2 + 3 + 4 + ... + n

Let me try with a small number. If n = 5:

1 + 2 + 3 + 4 + 5 = 15

But I want to think in recursion style — meaning I want to express the problem in terms of a smaller problem. So I think like this:

sum(5) = 5 + sum(4)
sum(4) = 4 + sum(3)
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1

Now I see a pattern:

sum(n) = n + sum(n-1)

This is exactly like factorial logic, but instead of multiply, we add.

Base Case (Very Important)​

Recursion must stop somewhere. When should it stop?

If n == 0 → sum = 0
If n == 1 → sum = 1

So base case can be:

if n == 0 → return 0

So the Recursion Logic Becomes​

Think in recursion template:

function sum(n):
if n == 0:
return 0
return n + sum(n-1)

That’s the whole recursion.

Dry Run (Very Important)​

Let’s calculate sum(5).

sum(5)
= 5 + sum(4)
= 5 + (4 + sum(3))
= 5 + (4 + (3 + sum(2)))
= 5 + (4 + (3 + (2 + sum(1))))
= 5 + (4 + (3 + (2 + (1 + sum(0)))))
= 5 + 4 + 3 + 2 + 1 + 0
= 15

Recursion goes down to 0, then values return back and add.

  • In factorial → values return and multiply
  • In sum → values return and add

Recursion Tree​

Let’s draw the recursion tree for sum(5)

### Recursive Calls (Going Down)
```java
sum(5)
└── sum(4)
└── sum(3)
└── sum(2)
└── sum(1)
└── sum(0)

Returning Phase (Coming Back Up)​

Now the base case is reached that is sum(0) = 0 Now values return back one by one:

sum(1) = 1 + sum(0) = 1
sum(2) = 2 + sum(1) = 3
sum(3) = 3 + sum(2) = 6
sum(4) = 4 + sum(3) = 10
sum(5) = 5 + sum(4) = 15

Full Recursion Flow (Tree View with Returns)​

sum(5)
|
|-- sum(4)
| |
| |-- sum(3)
| | |
| | |-- sum(2)
| | | |
| | | |-- sum(1)
| | | | |
| | | | |-- sum(0) = 0
| | | |
| | | |<- returns 1
| | |
| | |<- returns 3
| |
| |<- returns 6
|
|<- returns 10
Final return = 15
  • Factorial → multiply while returning
  • Sum → add while returning
  • Print → print before or after call depending on order

Pseudocode​

sum(n):
if n == 0:
return 0
else:
return n + sum(n-1)

Edge Cases​

Think like interviewer:

  • n = 0 → sum = 0
  • n = 1 → sum = 1
  • n < 0 → invalid input
  • Large n → stack overflow due to recursion depth
  • Sum may overflow integer for very large n

Time Complexity​

How many recursive calls?

sum(n)
sum(n-1)
sum(n-2)
...
sum(0)

Total calls = n
Time Complexity = O(n)

Space Complexity​

Because recursion stack stores function calls:

sum(n)
sum(n-1)
sum(n-2)
...

Stack depth = n
Space Complexity = O(n)

Very Important Pattern You Should Notice​

These recursion formulas are extremely important:

ProblemRecursive RelationWhat Happens
Factorialn × fact(n-1)Multiply while returning
Sum of nn + sum(n-1)Add while returning
Fibonaccif(n-1) + f(n-2)Two recursive calls
Print n to 1print(n), f(n-1)Work before call
Print 1 to nf(n-1), print(n)Work after call

These are recursion fundamentals and will be used everywhere later (trees, DP, backtracking).