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: linear-scan addition-accumulator input-size-reduction-by-one shared-state using-index-in-base-case reduce-operation augmented-assignment reduce

Write a function to sum all the elements in an array.

Iterative Solution

The iterative version shows the Addition Accumulator in action:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def sum(a)
  result = 0
	
  for i in (0..a.size - 1)
    result += a[i]
  end
  
  return result
end

a = [1,2,3,4]
p sum(a)

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sum_while(a)
  sum = 0
  i = 0
  
  while i < a.size
    sum += a[i]  
    i += 1
  end
  
  sum  
end

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sum(a)
  if a.size == 0
    return 0
  end
  
  n = a.shift
  
  return n + sum(a)
end

p sum([1,2,3,4])

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def sum(a, size)
  if size == 0
    return 0
  end
  
  last = a[size - 1]
  rest = sum(a, size - 1)
  
  return last + rest
end

a = [1,2,3,4]
size = a.size
p sum(a, size)

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def sum(a, size, sum, index)
  if size == index
    return sum
  end

  sum += a[index]

  return sum(a, size, sum, index + 1)
end

a = [1,2,3,4]
size = a.size
p sum(a, size, 0, 0)

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

1
2
3
4
5
6
7
8
9

def sum_recurse(a, i, sum)
  if i == a.size
    return sum
  end
  
  sum += a[i]
  
  sum_recurse(a, i+1, sum)  
end

Similar Problem

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

1
2
3
4
5
6
7
8
9

def sum(n)
  result = 0

  for i in (1..n)
    result += i
  end
  
  result
end

The formula based implementation:

1
2
3

def sum(n)
  n * (n-1)/2
end

Harmonic Number

The harmonic number is calculated using the formula:

H(N) = 1+1/2+1/3+…+1/N

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def harmonic(n)
  sum = 0.0
  
  for i in (1..n)
    sum += 1.0/i
  end
  
  return sum
end

p harmonic(6)

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