«Уровень стека слишком глубокий» с функцией Аккермана в Ruby

Question

Я использую Ruby v1.9.1 для написания программы с функцией Аккермана для моего класса в университете.Код следующий:

def ackermann(n,m)
  if n == 0 && m > 0
    return m+1
  elsif n > 0 && m == 0
    return ackermann(n-1,1)
  elsif n > 0 && m > 00
    return ackermann(n-1,ackermann(n,m-1))
  else
    puts "Wrong input, m and n must be higher than 0"
  end
end

puts ackermann(5,5)

Это очень рекурсивная функция.Поэтому я получаю сообщение об ошибке «Уровень стека слишком глубокий (SystemStackError)».Есть ли способ или способ исправить эту ошибку?

Answer 1

Вы можете переписать его в нерекурсивную функцию, чтобы он не исчерпал пространство стека, но был совершенно бессмысленным.

Посмотрите на диапазон этих значений.

Answer 2

Запоминание рекурсивных вызовов.Создайте карту {[int, hyperlong] => hyperlong} s, чтобы использовать подход динамического программирования для исчерпания стекового пространства.

Вот пример C ++: http://pastebin.com/tVQ7yB31

Известноошибки: ack (3, 10) использует более 3 ГБ оперативной памяти.

Answer 3

Хвост-рекурсивные алгоритмы (я боюсь, что 6-я строка в вашем алгоритме делает его нерекурсивным), может использовать TCO (оптимизация вызова хвоста). Чтобы включить его в Ruby 1.9:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false,
}

По словам ребят из LtU, алгоритм может быть записан как хвост-рекурсивный:

http://lambda -the-ultimate.org / узел / 2673