Why does one of these Ruby methods result in 'stack overflow' but the other doesn't? (Permutations Algorithm) -

below 2 different methods listing lexicographic permutations of n objects. can't understand why first method works fine smallish n, fails above limit , results in 'stack overflow'. second method; however, works fine tested limit of 10**6. in advance , insight!

$count = 0 $permutations = []    def perms(array)         $permutations = array      $count += 1       if array.length <= 1         return $permuations      end       = (array.length - 2)      until array[i] < array[i+1]         -= 1          end       if < 0         return $permutations      end       j = (array.length - 1)      until array[j] > array[i]         j -= 1      end       array[i], array[j] = array[j], array[i]       += 1      j = (array.length - 1)      until j <         array[i], array[j] = array[j], array[i]         += 1         j -= 1      end       while $count <= (10**6)-2         perms(array)      end   end    perms([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])   print $permutations 

and here's second method...

perm_limit = (10**6)  $count = 1   def perms(array)    if array.length <= 1       return false    end     = (array.length - 2)    until array[i] < array[i+1]       = (i - 1)    end     if < 0       return false    end     j = (array.length - 1)    until array[j] > array[i]       j = (j - 1)    end     array[i], array[j] = array[j], array[i]     = (i + 1)    j = (array.length - 1)     until j <       array[i], array[j] = array[j], array[i]       = (i + 1)       j = (j - 1)    end     $count += 1      return true end  array = [0,1,2,3,4,5,6,7,8,9]  while perms(array) == true    if $count == perm_limit       print array    end end     

again, thanks.

the first code sample provide recursive function:

 while $count <= (10**6)-2     perms(array)  end 

the function calling itself, calling itself, calling until stack overflows (everytime function called, space on stack allocated).

your second algorithm not use recursive function , depth of stack 1 - stack not growing.

for more information see "what stack overflow". question java, concept same stack-based languages.

recursive vs. iterative

so why writing recursive functions/algorithms if can overflow? because recursion can model problems nicely, , can easier write recursive algorithm (it's considered more "mathematically beautiful") iterative one. if know recursion depth won't deep, recursion might preferred method.

on other hand, iterative algorithm preferred if you're worried stack space. iterative function can easier or harder write depending on how model problem. all recursive functions can converted iterative functions.

on side note: there languages recursion , stack space not problem. these languages may use "tail-calls" meaning function recursive, instead of allocating new space on stack, re-uses current function's stack space (and stack never grows). can read more here.