Ruby getting into recursion

So, can someone please explain how this solves the problem?

I don't understand how it is getting #array.sum, by calling itself and just repeating #array[0] + sum_array(array[1..-1]). I'm aware it works itself down until the array == 0 , and then work's itself back??

Can someone trace me threw the steps?

Example:

# sum_array([])             # => 0
# sum_array([5])            # => 5
# sum_array([5, 2])         # => 7
# sum_array([4, 10, -1, 2]) # => 15

#??################################??#
def sum_array(array)
return 0 if array.empty?

array[0] + sum_array(array[1..-1])
end
#??###############################??#

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)