Write a recursive function sum(n) that calculates the sum of all odd numbers in an array arr up to index n.
Concepts
- Recursion: Repeatedly check whether
arr[n]is odd, and add it only if true. - Base Case: If
n == 0, returnarr[0]if it’s odd, otherwise0. - Recursive Case: Return
(arr[n] if odd) + sum(n - 1).
Time & Space Complexity
- Time Complexity:
O(n) - Space Complexity:
O(n)(recursive call stack)
Examples
Input: [5, 2, 6, 1, 3]
Odd numbers: 5, 1, 3
Output: 9Approach
- Check if
arr[n]is odd. - If yes, add it to recursive result of
sum(n-1). - Else, skip it and continue recursion.
let arr = [5, 2, 6, 1, 3];
function sum(n) {
let isOdd = arr[n] % 2 !== 0;
if (n === 0) return isOdd ? arr[0] : 0;
return (isOdd ? arr[n] : 0) + sum(n - 1);
}
console.log(sum(arr.length - 1)); // Output: 9
#include <stdio.h>
int sum(int arr[], int n) {
int isOdd = arr[n] % 2 != 0;
if (n == 0) return isOdd ? arr[0] : 0;
return (isOdd ? arr[n] : 0) + 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)); // Output: 9
return 0;
}
#include <iostream>
using namespace std;
int sum(int arr[], int n) {
bool isOdd = arr[n] % 2 != 0;
if (n == 0) return isOdd ? arr[0] : 0;
return (isOdd ? arr[n] : 0) + 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; // Output: 9
return 0;
}
public class Main {
public static int sum(int[] arr, int n) {
boolean isOdd = arr[n] % 2 != 0;
if (n == 0) return isOdd ? arr[0] : 0;
return (isOdd ? arr[n] : 0) + 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)); // Output: 9
}
}
def sum_odd(arr, n):
is_odd = arr[n] % 2 != 0
if n == 0:
return arr[0] if is_odd else 0
return (arr[n] if is_odd else 0) + sum_odd(arr, n - 1)
arr = [5, 2, 6, 1, 3]
print(sum_odd(arr, len(arr) - 1)) # Output: 9
using System;
class Program {
static int Sum(int[] arr, int n) {
bool isOdd = arr[n] % 2 != 0;
if (n == 0) return isOdd ? arr[0] : 0;
return (isOdd ? arr[n] : 0) + Sum(arr, n - 1);
}
static void Main() {
int[] arr = {5, 2, 6, 1, 3};
Console.WriteLine(Sum(arr, arr.Length - 1)); // Output: 9
}
}
