Write a function sum(n) that calculates the sum of the first n natural numbers using recursion.
Concepts
- Recursion: A technique where a function calls itself with a reduced subproblem.
- Base Case: Stops recursion to prevent infinite calls. Here, if
n === 0, return 0. - Recursive Case: Return
n + sum(n - 1).
Time & Space Complexity
- Time Complexity:
O(n)– one call per value from n to 0. - Space Complexity:
O(n)– due to call stack in recursion.
Examples
Input: 5
Output: 15
// 5 + 4 + 3 + 2 + 1 = 15Approach
- If
n === 0, return 0 (base case). - Otherwise, return
n + sum(n - 1).
function sum(n) {
if (n === 0) return 0;
return n + sum(n - 1);
}
console.log(sum(5)); // 15
#include <stdio.h>
int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main() {
printf("%d\n", sum(5)); // 15
return 0;
}
#include <iostream>
using namespace std;
int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main() {
cout << sum(5) << endl; // 15
return 0;
}
public class Main {
public static int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
public static void main(String[] args) {
System.out.println(sum(5)); // 15
}
}
def sum_n(n):
if n == 0:
return 0
return n + sum_n(n - 1)
print(sum_n(5)) # 15
using System;
class Program {
static int Sum(int n) {
if (n == 0) return 0;
return n + Sum(n - 1);
}
static void Main() {
Console.WriteLine(Sum(5)); // 15
}
}
