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
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.
/*
* 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)
- What is the sum of no numbers?
- How deep does the recursion go?