I am having trouble understanding this simple recursion problem

Question

This code is from "The Bastards Book of Ruby" and all it does is find the largest number. It is given as an example to try understand recursion. http://ruby.bastardsbook.com/chapters/recursion/

def rock_judger(rocks_arr)    
  if rocks_arr.length <= 2  # the base case
    a = rocks_arr[0]
    b = rocks_arr[-1]
  else
    a = rock_judger(rocks_arr.slice!(0,rocks_arr.length/2))
    b = rock_judger(rocks_arr)
  end    
  return a > b ? a : b
end

To test it, I called the method with the array [1, 2, 3, 4, 30, 31, 32, 34] and investigated what is happening exactly using the pry-byebug gem.

The first time it runs, it runs the slice! method on the array, and we get [1,2,3,4]. This again runs, and it does the slice! method again, returning [1,2]. Then at this point, it assigns a = 1 and b = 2.

Now here we reach the return method. 2 > 1, so it returns b. But instead of returning just the integer 2, it goes back to line 15!

My question is, how is this possible? Should this not just return 2?

Answer 1

It's easy to get mixed up when trying to trace what is happening with a recursion. As well as adding "puts" statements, it's helpful to use indentation to isolate different instances of the recursion. See if the following helps.

INDENT = 8

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

def rock_judger(rocks_arr)    
  indent
  puhline
  pu "rock_judger called with argument #{rocks_arr}"
  pu "rocks_arr.length = #{rocks_arr.length}"
  if rocks_arr.length <= 2  # the base case
    pu "rocks_arr.length <= 2"
    a = rocks_arr[0]
    b = rocks_arr[-1]
    pu "a = #{a}, b = #{b}"
  else
    pu "rocks_arr.length > 2"
    pu "calling rock_judger(#{rocks_arr.dup.slice!(0,rocks_arr.length/2)})"
    a = rock_judger(rocks_arr.slice!(0,rocks_arr.length/2))
    pu "rock_judger returned #{a}"         
    pu "calling rock_judger(#{rocks_arr})"
    b = rock_judger(rocks_arr)
    pu "rock_judger returned #{b}"         
  end 
  c = a > b ? a : b
  pu "a > b ? a : b = #{c}"
  pu "returning #{c}"
  puhline
  undent
  c
end

---

rocks_arr = [1, 2, 3, 4, 30, 31, 32, 34] 

rock_judger(rocks_arr)
  #=> 34

The following is displayed.

rock_judger called with argument [1, 2, 3, 4, 30, 31, 32, 34]
rocks_arr.length = 8
rocks_arr.length > 2
calling rock_judger([1, 2, 3, 4])

        rock_judger called with argument [1, 2, 3, 4]
        rocks_arr.length = 4
        rocks_arr.length > 2
        calling rock_judger([1, 2])

                rock_judger called with argument [1, 2]
                rocks_arr.length = 2
                rocks_arr.length <= 2
                a = 1, b = 2
                a > b ? a : b = 2
                returning 2

        rock_judger returned 2
        calling rock_judger([3, 4])

                rock_judger called with argument [3, 4]
                rocks_arr.length = 2
                rocks_arr.length <= 2
                a = 3, b = 4
                a > b ? a : b = 4
                returning 4

        rock_judger returned 4
        a > b ? a : b = 4
        returning 4

rock_judger returned 4
calling rock_judger([30, 31, 32, 34])

        rock_judger called with argument [30, 31, 32, 34]
        rocks_arr.length = 4
        rocks_arr.length > 2
        calling rock_judger([30, 31])

                rock_judger called with argument [30, 31]
                rocks_arr.length = 2
                rocks_arr.length <= 2
                a = 30, b = 31
                a > b ? a : b = 31
                returning 31

        rock_judger returned 31
        calling rock_judger([32, 34])

                rock_judger called with argument [32, 34]
                rocks_arr.length = 2
                rocks_arr.length <= 2
                a = 32, b = 34
                a > b ? a : b = 34
                returning 34

        rock_judger returned 34
        a > b ? a : b = 34
        returning 34

rock_judger returned 34
a > b ? a : b = 34
returning 34