Хвостовая рекурсия в ruby ​​- в чем разница между этими двумя реализациями? - PullRequest
Новая
       0

Хвостовая рекурсия в ruby ​​- в чем разница между этими двумя реализациями?

3 голосов
/ 24 мая 2011

Я новичок в Ruby и только начал изучать язык пару дней назад. В качестве упражнения я попытался реализовать простую быструю сортировку 

class Sort
  def swap(i,j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def quicksort(lower=0, upper = @data.length - 1)
    return nil if lower >= upper
    m = lower
    i = 0
    ((lower+1)..upper).each do |i|
      swap(++m, i) if @data[i] < @data[lower]
    end

    swap(m, lower)

    quicksort1(lower, m -1)
    quicksort1(m+1, upper)
  end
end

Вызов быстрой сортировки, скажем, 10000 целых чисел дает мне ошибку на уровне стека. После поиска в Google я понял, что хвостовая рекурсия еще не поддерживается в Ruby ( вид ). Но потом я нашел следующий фрагмент (из здесь ) 

def qs(v)
  return v if v.nil? or v.length <= 1
  less, more = v[1..-1].partition { |i| i < v[0] }
  qs(less) + [v[0]] + qs(more)
end

Запуск второго фрагмента отлично работает даже с миллионами целых чисел. Тем не менее, насколько я могу судить, в конце есть хвостовая рекурсия. Так чего я тут не понимаю?

1 Ответ

9 голосов
/ 24 мая 2011

Ни один из показанных вами методов не является хвостовым рекурсивным (ну, технически первый из них является наполовину хвостовым рекурсивным: второй рекурсивный вызов является хвостовым, но первый - нет - второй метод не является хвостовым рекурсивным ввсе).

Причина, по которой первый метод переполняет стек, а второй - нет, состоит в том, что первый метод повторяется намного глубже второго (линейно, а не логарифмически) из-за ошибки (++mпросто применяет унарный оператор + к m дважды - на самом деле он ничего не делает с m).

При наличии достаточно большого массива обе версии будут переполнены (и это произойдет, даже если ruby ​​действительно выполнитTCO), но без ошибки 10000 элементов недостаточно велики.

...