Sum Elements in an Array
excerpt: This covers the basic building blocks, Linear Scan, Addition Accumulator and Input Size Reduction by One, Shared State and Using Index in Base Case. tags: linearscan additionaccumulator inputsizereductionbyone sharedstate usingindexinbasecase reduceoperation augmentedassignment reduce
Write a function to sum all the elements in an array.
Iterative Solution
The iterative version shows the Addition Accumulator in action:


An accumulator is a variable used in a loop to add up or accumulate a result. An operation like this that combines a sequence of elements into a single value is called a reduce operation.
A statement that updates the value of a variable using an operator like = is called augmented assignment. In the sum method += updates the result variable.
Implementation using a while loop:


The terminating condition in the while loop is slightly modified in the recursive implementation and it becomes the base case. The unit of work is accumulating the sum in the sum variable.
Recursive Solution
If you can remove elements from the array, the recursive implementation has only one parameter.


Mutating the input data structure is usually not a good idea. Since the rest of the program might be depending on the values in the array.
A new parameter is added to the method that decides when the base case is reached.


The sum can be a shared state that is persisted across recursive calls by accumulating the added values in the sum variable. The additional parameters sum and index are added the sum method. The sum will contain the final result, which is returned when the base case is reached.
The sum and index are initialized to 0 to begin processing of the array elements. The recursive function does the addition before the recursive call. The index is incremented in the recursive call so the next recursive call knows which element it needs to add to the running sum.


This implementation is more complicated because we have additional parameters in the sum. Alternative recursive implementation:


Similar Problem
Write a function that takes a parameter n and returns the sum of the numbers 1 to n.


The formula based implementation:


Harmonic Number
The harmonic number is calculated using the formula:
H(N) = 1+1/2+1/3+…+1/N


The sum variable in this method uses floating point number.
Building Blocks
 Linear Scan
 Addition Accumulator
 Input Size Reduction by One
 Shared State
 Using Index in Base Case