Sum of an Array Using Recursion

Problem

Print the sum of all numbers in the array. Do not use a loop: use recursion. The sum can be bigger than a 32-bit number.

Constraints

  • 1 <= n <= 1000
  • |a[i]| <= 10^9

Examples

Input

5
1 2 3 4 5

Output

15

Solutions

Best approachTime O(n)Space O(n)

The base case is an empty rest, which sums to 0. Each call adds one number to the answer of a smaller problem. The recursion is n levels deep.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Recursive sum.
 * Input   : n, then n integers.
 * Output  : The sum.
 * Approach: One number at a time.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        private static long sumFrom(int[] a, int index) {
            if (index == a.length) {
                return 0;
            }
            return a[index] + sumFrom(a, index + 1);
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(int[] a) {
        // Step 1: The sum of the numbers from "index" onwards is a[index] plus the sum from index + 1.
        return sumFrom(a, 0);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}
Hints (2)
  1. What is the sum of no numbers?
  2. How deep does the recursion go?