🔄📚Intermediate

Sum of Natural Numbers Using Recursion

Sum using recursion

Calculate the sum of first n natural numbers (1 + 2 + 3 + ... + n) using recursion. Each call reduces the problem size until we reach the base case.

📐 Recursive Formula

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

Base case: sum(0) = 0

🔢 Example: sum(5)

sum(5) = 5 + 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!

Unwinding:

= 5 + 4 + 3 + 2 + 1 + 0 = 15

Program Code

sum_recursion.c

1#include <stdio.h>
2
3// Recursive function to calculate sum
4int sum(int n) {
5    if (n == 0) return 0;  // Base case: sum of 0 numbers = 0
6    return n + sum(n - 1); // Recursive case: n + sum of (n-1) numbers
7}
8
9int main() {
10    int n;
11    
12    printf("Enter n: ");
13    scanf("%d", &n);
14    
15    printf("Sum of first %d natural numbers = %d\n", n, sum(n));
16    
17    // Verify with formula: n*(n+1)/2
18    printf("Using formula: %d\n", n * (n + 1) / 2);
19    
20    return 0;
21}