Problem Statement:
Write a function sum(n) that calculates the sum of the first n natural numbers using recursion.
Example:
Input: 5
Process: 5 + 4 + 3 + 2 + 1 = 15
Output: 15
Concepts:
- Recursion: A technique where a
function callsitself with areduced subproblem. - Base Case:
Stops recursionto prevent infinite calls. Here, ifn === 0, return 0. - Recursive Case:
Return n + sum(n - 1).
Approach:
- Use
recursionto reduce the problem. - Base case: if
n === 0,return 0. - Recursive case:return
n + sum(n-1). - This keeps adding numbers until
nreaches0, giving the totalsum.
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.
function sum(n) {
if (n === 0) return 0;
return n + sum(n - 1);
}
console.log(sum(5)); // 15
def sum_n(n):
if n == 0:
return 0
return n + sum_n(n - 1)
print(sum_n(5)) # 15
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
}
}
#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;
}
#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;
}
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
}
}
