Count Zeroes in an Array

excerpt: This covers the basic building blocks, Counter, Capturing Return Value from Subproblem, Processing Return Value from Subproblem and Head Recursion. tags: counter capturing-return-value-from-subproblem processing-return-value-from-subproblem head-recursion

Write a function to count the number of zeroes in an input array.

Iterative Implementation

The iterative implementation to count zeroes in the input array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def count(a)
  result = 0
  
  for i in (1..a.size - 1)
    if a[i] == 0
      result += 1
    end  
  end
  
  result
end

p count([3,0,1,0,0,1,0])

Recursive Implementation

The recursive implementation to count zeroes in the input array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def count(a, size)
  if size == 0
    return 0
  end
  
  if a[size - 1] == 0
    @count += 1
  end
  
  count(a, size - 1)
end

a = [1,2,0,4,0,0]
size = a.size

@count = 0
count(a, size)
p @count

Using a variable such as count is not a good programming practice. We can implement a recursive method that does not use any count variable by using head recursion.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def count(a, size)
  if size == 0
    return 0
  end
  
  zeroes = count(a, size - 1)
  
  if a[size - 1] == 0
    zeroes += 1
  end
  
  return zeroes
end

a = [1,2,0,4,0,0]
size = a.size

p count(a, size)

The unit of work is performed after the recursive call. The output of the subproblem is captured in the zeroes local variable. The return value now is the number of zeroes. This implementation leans more towards functional programming. The focus is on the input and output to the recursive function. There is no mutation of state outside of the recursive function. This approach is a better coding practice.

Building Blocks

Counter
Capturing Return Value from Subproblem
Processing Return Value from Subproblem
Head Recursion