Ruby getting into recursion

In Ruby, array[1..-1] is the same as array except the first element has been removed from the array.

So array[0] + sum_array(array[1..-1]) means "add the first element to the sum of every element other than first element". If you think it about, that is equivalent to just adding up each element in the array. (Addition is supposed to be associative, so it's valid to add up the last elements in the array first instead of starting by adding the first two elements.)

You could write it out as math equations like this:

(a + b + c + d) = a + (b + c + d) = a + (b + (c + d))

You can trace through the steps yourself if you add some simple puts debugging commands like this:

def sum_array(array)
  return 0 if array.empty?
  puts "sum_array called with #{array.inspect}"
  tail = sum_array(array[1..-1])
  puts "sum_array returning #{array[0]} + #{tail}"
  array[0] + tail
end

sum_array([2, 4, 7, 8])

@David's answer can be enhanced by separating the various instances of the method by indenting. Here all code that begins in the same column corresponds to the same instance of the method.

INDENT = 6
$col = -INDENT
def indent; $col += INDENT; end
def undent; $col -= INDENT; end
def pu(s); puts "#{" "*$col}#{s}"; end 
def puhline; pu('-'*(65-$col)); end

def sum_array(array)
  indent
  puhline
  pu "sum_array called with argument array = #{array.inspect}"
  if array.empty?
    pu "returning 0 as array is empty"
    puhline
    undent
  end
  return 0 if array.empty?
  pu "calling sum_array(#{array[1..-1].inspect})"
  tail = sum_array(array[1..-1])
  pu "sum_array returned tail = #{tail.inspect}"
  pu "returning array[0] + tail = #{array[0] + tail}"
  puhline
  undent
  array[0] + tail
end

sum_array([2, 4, 7, 8])
  #=> 21

The following is displayed.

-----------------------------------------------------------------
sum_array called with argument array = [2, 4, 7, 8]
calling sum_array([4, 7, 8])
      -----------------------------------------------------------
      sum_array called with argument array = [4, 7, 8]
      calling sum_array([7, 8])
            -----------------------------------------------------
            sum_array called with argument array = [7, 8]
            calling sum_array([8])
                  -----------------------------------------------
                  sum_array called with argument array = [8]
                  calling sum_array([])
                        -----------------------------------------
                        sum_array called with argument array = []
                        returning 0 as array is empty
                        -----------------------------------------
                  sum_array returned tail = 0
                  returning array[0] + tail = 8
                  -----------------------------------------------
            sum_array returned tail = 8
            returning array[0] + tail = 15
            -----------------------------------------------------
      sum_array returned tail = 15
      returning array[0] + tail = 19
      -----------------------------------------------------------
sum_array returned tail = 19
returning array[0] + tail = 21
-----------------------------------------------------------------

To understand recursion, you must first understand recursion. Just kidding, kind of. I'll give a slightly different answer than those here.

Imagine that we expressed this in another language, say Scheme/Lisp... Also imagine we have three functions:

• (null? a) which tells us if the array a is empty/null.
• (car a) which returns the first element of the array a.
• (cdr a) which returns the rest of the array/list.
• Oh and addition is weird too (+ 1 2) == 3

; If `a` is empty, the sum is 0.
; Otherwise, the sum is the first item plus
; the result of calling sum on the rest of the list.
(define (sum a)
  (if (null? a)
    0
    (+ (car a) (sum (cdr a)))))

We can trace the call to (sum '(1 2 3 4)):

(sum '(1 2 3 4))
(+ 1 (sum '(2 3 4)))
(+ 1 (+ 2 (sum '(3 4))))
(+ 1 (+ 2 (+ 3 (sum '(4)))))
(+ 1 (+ 2 (+ 3 (+ 4 (sum '())))))
(+ 1 (+ 2 (+ 3 (+ 4 0))))
(+ 1 (+ 2 (+ 3 4)))
(+ 1 (+ 2 7))
(+ 1 9)
(10)

I think it is easiest to understand in the way you would understand any recursive definitions in mathematics (think about the famous Fibonacci sequence, as example), or mathematical proofs by induction.

In those you establish a base case, and then have a formula which reduces a more complicated case to a simpler case.

For instance, in the Fibonacci case, you would write in mathematics something like:

fib 0 = 0
fib 1 = 1
n>1 : fib n = fib(n-1)+fib(n-2)

In your sum example, you would have likewise

sum [] = 0
sum [x:xs] = x + sum xs

You code is virtually a direct translation of these mathematical formulas into Ruby.

Having said this, your function would be more idiomatically expressed by

def sum_array(array)
  array.reduce(&:+)
end

This is because your recursion pattern is so commonplace, that the Ruby class Enumerable (which Array is a subclass of) contains a generic reduce method for such a case. Have a look at the Ruby docs to see, what else you can do with reduce.

We can gain deeper understanding and appreciation for recursive algorithms by applying inductive reasoning -

1. If the input a is empty, return the empty sum, 0
2. (inductive) a has at least one element. Add the first element a[0] to the result of the recursive sub-problem sum a[1..] and return

def sum a
  if a == [] then
    0                    # 1
  else
    a[0] + (sum a[1..])  # 2
  end
end

puts (sum [1,2,3])

6

Recursion is a functional heritage and in functional style we can replace any expression with its return value. This is known as referential transparency. Using this property we can see how sum behaves -

sum [1,2,3]
== [1,2,3][0] + (sum [1,2,3][1..])
== 1 + (sum [2,3])
== 1 + [2,3][0] + (sum [2,3][1..])
== 1 + 2 + (sum [3])
== 1 + 2 + [3][0] (sum [3][1..])
== 1 + 2 + 3 (sum [])
== 1 + 2 + 3 + 0
== 1 + 2 + 3
== 1 + 5
== 6

Or we could write psum that draws the visualization for us. The same inductive reasoning can be applied -

def psum a
  if a == [] then
    "0"                           # 1
  else
    "(#{a[0]} + #{psum a[1..]})"  # 2
  end
end

puts (psum [1,2,3])

(1 + (2 + (3 + 0)))