Ruby: Recursion and order of execution

Question

The output of the below method is [6,4,2,0,0,2,4,6].

I understand everything up to the array=[6,4,2,0,0] at n-1 with array[4]=0 added at line no. 3. But I'm completely stumped on why the method continues to execute even after line no 3 is executed which should then return [6,4,2,0,0] to the original method call. Even more vexing is that n resets to n=1 and increments to n=2 and n=3...n=3 being the starting argument value passed in the method call.

Also, I'm having major problems understanding recursion in the various possibilities. An answer to this question and a suggestion on a 'recursion for dummies' would be greatly appreciated!

def append(array, n)
  return array if n < 0 #base case, how we end this thing
  array <<  n*2    #Line No. 1 

  append(array, n - 1) #Line No. 2 
  array <<  n*2    #Line No. 3

end
append( [], 3)

#output  [6,4,2,0,0,2,4,6]

the Tin Man · Accepted Answer · 2016-04-07 19:33:54Z

2

There is nothing mysterious about the order of execution here, and your counter doesn't get incremented. To understand what happens, let's walk through the code line by line. I'll take append([], 2) to make it quicker.

# you call append([], 2)
return array if n < 0
# n >= 0 so we continue
array <<  n*2
# array is now [4]
append(array, n - 1)
# you call append(array, 1) which will mutate array,
# lets call x what will be appended to it
# array is now [4, x]
array <<  n*2
# array is now [4, x, 4]
# you get [4, x, 4] as a returned value from the append method
# because after the first line there is no return statement,
# so the return value of the last line is returned

# let's now see what x, that is append(array, 1) is
return array if n < 0
# n >= 0 so we continue
array <<  n*2
# array is now [4, 2] because at that time, array is [4]
append(array, n - 1)
# you call append(array, 0) which will mutate array,
# lets call y what will be appended to it
# array is now [4, 2, y]
array <<  n*2
# array is now [4, 2, y, 2]
# this is what you return to the first method invocation
# so we can replace [4, x, 4] with [4, 2, y, 2, 4]

# let's now see what y, that is append(array, 0) is
return array if n < 0
# n >= 0 so we continue
array <<  n*2
# array is now [4, 2, 0] because at that time, array is [4, 2]
append(array, n - 1)
# you call append(array, -1) which will mutate array,
# lets call z what will be appended to it
# array is now [4, 2, 0, z]
array <<  n*2
# array is now [4, 2, 0, z, 0]
# this is what you return to the second method invocation
# so we can replace [4, 2, y, 2, 4] with [4, 2, 0, z, 0, 2, 4]

# now in the last invocation, z is nothing because -1 < 0,
# so nothing is appended to the array
# the first method invocation returns [4, 2, 0, 0, 2, 4]

The return statement only returns from its immediate method invocation. The fact that a method is recursive doesn't change that. It will not somehow find the top level invocation of itself and return from it.

If I can give you an advice when working with recursion, it would be to not mutate your arguments. Working with pure functions is much easier and intuitive, especially in this context. This is how your append method would look like without mutations :

def append n
    return n < 0 ? [] : [n * 2, append(n - 1), n * 2].flatten
end

and you would call it like this :

array = append(3)
# [6, 4, 2, 0, 0, 2, 4, 6]

This way your array doesn't get mutated and you get a much clearer image of what the method returns.

In case you don't find it clearer, visualize it this way

# append(3)
[6,
    # append(2)
    [4,
        # append(1)
        [2, 
            # append(0)
            [0,
                # append(-1)
                []
            , 0].flatten
        , 2].flatten
    , 4].flatten
, 6].flatten

edited Apr 7, 2016 at 19:33

the Tin Man

161k44 gold badges222 silver badges308 bronze badges

answered Apr 7, 2016 at 18:56

VonD

5,1452 gold badges22 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

bscottyoung Over a year ago

What happens to this visualization if I insert after line no. 'array << n*3'? This creates a nesting of recursions??

VonD Over a year ago

@bscottyoung if you insert this after which line ?

VonD Over a year ago

@bscottyoung this is what happens : gist.github.com/VonD/4a63f7ee589beddfe8eebba2d4a70c2e, it doesn't create a nesting of recursions, as this line doesn't call the method it comes from. A nesting of recursions would be a call to something like append(append([], 2), 3)

user229044 · Accepted Answer · 2016-04-07 18:30:04Z

The method is invoked many times. Talking about how "the method continues to execute" already demonstrates that you're not thinking about this incorrectly.

Each invocation of the method is completely independent of every other invocation, and each invocation has a unique copy of n with its own value. The method is invoked four times, and each of those four invocation pushes two items into the array, yielding eight total items.

The key to undertanding what is happening is that each method invocation pushes a number onto the array, and then invokes itself, and then pushes another number onto the array. Both "6" entires are pushed by the same method invocation, and they wrap all of the other entries because the recursion happened between the two array << n*2 calls in the method where n was 6.

Consider the following:

def method_a
  puts "A start"
  method_b
  puts "A end"
end

def method_b
  puts " B start"
  method_c
  puts " B end"
end

def method_c
  puts "  C start"
  puts "  !!!"
  puts "  C end"
end

method_a

This is not recursive, but it behaves in a similar manner. The output of this code is:

A start
 B start
  C start
  !!!
  C end
 B end
A end

This is as opposed to what you seem to expect to see:

A start
 B start
  C start
  !!!

Each function outputs a "start" line, invokes its next function, and then when the nested invocation returns, it outputs its "end" line. This is exactly how your recursive function behaves. Each invocation continues to execute after the nested invocation returns. The local value of n is unchanged, and it gets pushed onto the array a second time.

Now that I'm getting a better understanding of the mechanics of recursion, how do you determine how and when to use it? I understand the notion of parsing the kings rocks, but I sure would like to find a resource that discusses various uses. Any ideas?

Silver Phoenix · Accepted Answer · 2016-04-07 18:53:31Z

I think you have the idea that return ends everything, but that is not the case.

Here is what is happening, step by step:

append(array = [], n = 3)                 # initial call
  array << 6                              #Line No. 1
  append(array = [6], n = 2)              #Line No. 2
    array << 4                            #Line No. 1
    append(array = [6,4], n = 1)          #Line No. 2
      array << 2                          #Line No. 1
      append(array = [6,4,2], n = 0)      #Line No. 2
        array << 0                        #Line No. 1
        append(array = [6,4,2,0], n = -1) #Line No. 2
          return array                    #base case
          # but `return` doesn't leave the recursion.
          # it only goes up one step in the call stack, like so:
        array << 0                        #Line No. 3 -> array = [6,4,2,0,0]
      array << 2                          #Line No. 3 -> array = [6,4,2,0,0,2]
    array << 4                            #Line No. 3 -> array = [6,4,2,0,0,2,4]
  array << 6                              #Line No. 3 -> array = [6,4,2,0,0,2,4,6]

I think that Line No. 3 introduced some confusion. If it was simply n*2, you would have seen that in the end it didn't return the array, but instead a Fixnum. Here is a shortened version of the step by step for this case:

append([], 3)  # initial call
  array << 6; append([6], 2)
    array << 4; append([6,4], 1)
      array << 2; append([6,4,2], 0)
        array << 0; append([6,4,2,0], -1)
          return array
        0               # result of n*2 (Line No. 3)
      2                 # result of n*2 (Line No. 3)
    4                   # result of n*2 (Line No. 3)
  6                     # result of n*2 (Line No. 3)

#output = 6

On the other hand, if you remove Line No. 3, the last line will be the result from a call to append, which in effect will coincide with the base case.

append([], 3)   # initial call
  array << 6; append([6], 2)
    array << 4; append([6,4], 1)
      array << 2; append([6,4,2], 0)
        array << 0; append([6,4,2,0], -1)
          return array
        array           # result from the call append([6,4,2], 0) (Line No. 2)
      array             # result from the call append([6,4], 1)   (Line No. 2)
    array               # result from the call append([6], 2)     (Line No. 2)
  array                 # result from the call append([], 3)      (Line No. 2)

#output = [6,4,2,0]

Recursion seems to create a nesting that must unwind step by step...Last in First Out??

Collectives™ on Stack Overflow

Ruby: Recursion and order of execution

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related