CODEWITHSUNDEEP
rubyfunctionrecursionreturn
Don Beto
Don Beto

Reputation: 132

Trouble understanding recursion in Ruby

I'm following a video about recursion, it's in Ruby

First, the code to append a sequence to an array is easy to understand:

def append(ary, n)
  return ary if n < 0
  ary << n
  append(ary, n-1)
end

append([], 5)
=> [5, 4, 3, 2, 1, 0]

The thing I don't understand is when the reverse_append function is presented:

01 def reverse_append(ary, n)
02   return ary if n < 0
03   reverse_append(ary, n-1)
04   ary << n
05   return ary
06 end

I understand the function reverse_append does this:

What I don't understand is why line 04 executes at all if line 02 says that if n is less than 0 then return the array, (which would be empty for what I understand). What's the flow chart for this?

Upvotes: 0

Views: 68

Answers (2)

pjs
pjs

Reputation: 19854

Your reverse_append can be rewritten as:

def reverse_append(ary, n)
  return ary if n < 0
  reverse_append(ary, n-1)
  ary << n
end

which makes it more obvious that the difference from append(ary, n) is the order in which you do << vs. the recursive call. append() says "If I haven't gotten to a negative value, concatenate my n to the array, and then get the array that results from concatenating all smaller values of n and return it", while reverse_append() says "If I haven't gotten to a negative value, get the array that results from concatenating all smaller values of n, and then concatenate my n to the result and return it." If you think about it for a bit, you should see that that determines the order in which the values get appended.

Upvotes: 1

Meier
Meier

Reputation: 3880

The key to recursion: there are many invocations of the same function active. each invocation has its own local variables. The return only return from the current innvovcation.

The calling function tree will look like this

reverse_append([], 2)
..reverse_append([], 1)
....reverse_append([], 0)
......reverse_append([], -1)
......returns []
....[] << 0
....returns [0]
..[0] << 1
..-> [0, 1]
 [0, 1] << 2
 -> [0, 1, 2]

Upvotes: 1

Related Questions