Write a function sum(n) that calculates the sum of all numbers in an array arr using recursion. It sums from index 0 to n.
Concepts
- Recursion: The function keeps summing the element at index
nand calls itself withn-1. - Base Case: If
n == 0, return the first element. - Recursive Case: Return
arr[n] + sum(n - 1).
Time & Space Complexity
- Time Complexity:
O(n)– one recursive call per element. - Space Complexity:
O(n)– due to call stack.
Examples
Input: [5, 2, 6, 1, 3]
Output: 17
// 5 + 2 + 6 + 1 + 3 = 17Approach
- If
n == 0, returnarr[0]. - Otherwise, return
arr[n] + sum(n - 1).
let arr = [5, 2, 6, 1, 3];
function sum(n) {
if (n === 0) return arr[0];
return arr[n] + sum(n - 1);
}
console.log(sum(arr.length - 1)); // 17
#include <stdio.h>
int sum(int arr[], int n) {
if (n == 0) return arr[0];
return arr[n] + sum(arr, n - 1);
}
int main() {
int arr[] = {5, 2, 6, 1, 3};
int len = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", sum(arr, len - 1)); // 17
return 0;
}
#include <iostream>
using namespace std;
int sum(int arr[], int n) {
if (n == 0) return arr[0];
return arr[n] + sum(arr, n - 1);
}
int main() {
int arr[] = {5, 2, 6, 1, 3};
int len = sizeof(arr) / sizeof(arr[0]);
cout << sum(arr, len - 1) << endl; // 17
return 0;
}
public class Main {
public static int sum(int[] arr, int n) {
if (n == 0) return arr[0];
return arr[n] + sum(arr, n - 1);
}
public static void main(String[] args) {
int[] arr = {5, 2, 6, 1, 3};
System.out.println(sum(arr, arr.length - 1)); // 17
}
}
def sum_array(arr, n):
if n == 0:
return arr[0]
return arr[n] + sum_array(arr, n - 1)
arr = [5, 2, 6, 1, 3]
print(sum_array(arr, len(arr) - 1)) # 17
using System;
class Program {
static int Sum(int[] arr, int n) {
if (n == 0) return arr[0];
return arr[n] + Sum(arr, n - 1);
}
static void Main() {
int[] arr = {5, 2, 6, 1, 3};
Console.WriteLine(Sum(arr, arr.Length - 1)); // 17
}
}
