Problem Statement:
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.
Example:
Input: [5, 2, 6, 1, 3]
Process: 5 + 2 + 6 + 1 + 3 = 17
Output: 17
Concepts:
- Recursion: The function keeps summing the element at index
nandcallsitself withn-1. - Base Case: If
n == 0, return thefirst element. - Recursive Case:
Return arr[n] + sum(n - 1).
Approach:
- If
n == 0, return arr[0]. - Otherwise, 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.
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
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
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
}
}
#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;
}
#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;
}
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
}
}
