Почему добавление 1 к рекурсивному вызову proc возвращает количество выполненных вызовов?

Question

Предположим, у меня есть этот код:

def rcall(num)
  return 0 if 10 == num
  1 + rcall(num - 1)
end

p rcall(90) # => 80

Этот код всегда будет возвращать на 10 меньше, чем значение, переданное в num, то есть количество выполненных рекурсивных вызовов.

Я не вижу, как это работает.Я смутно понимаю, что мы возвращаем ноль, если выполняется условие выхода, чтобы не увеличивать счетчик снова.Но как, собственно, добавление единицы к вызову proc увеличивает количество вызываемых вызовов?Я не вижу, где накапливается инкрементатор.

Кроме того, это метод, специфичный для архитектуры Ruby, или он более применим?Я не встречал упоминания в ответах на вопросы о том, как считать рекурсивные вызовы;Кажется, большую часть времени люди передают переменную counter, чтобы отследить счет.

Answer 1

Скажем, вы изменили базовое условие на return 0 if num.zero?, затем вызов его с аргументом 3 будет выглядеть так:

1 + rcall(2)
    # => 1 + rcall(1)
             # => 1 + rcall(0)
                      # => 0

, что, если вы замените вызовы rcall их результатами (начиная сснизу), выходит на 1 + 1 + 1 + 0

Другими словами, вы можете понять это немного легче, перейдя от базового случая вверх:

rcall(0)
# 0

rcall(1)
# the same as 1 + rcall(0), which is one

rcall(2)
# the same as 1 + rcall(1), which is two.

Надеюсь, вы увидите шаблон.

Как уже упоминалось в комментариях, вы можете оптимизировать его следующим образом:

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

def rcall(num, sum=0)
  return sum if 10 == num
  rcall(num - 1, sum + 1)
end

Хотя для этого могут потребоваться другие настройки, я не совсем уверен.

См. Что такое оптимизация Tail Call?

Answer 2

Это не совсем так. Важной частью является то, что rcall всегда возвращает 0, когда он не выполняет рекурсивный вызов. Из-за этого вы можете добавить 1 к rcall, когда вызываете его рекурсивно. Вы получаете за каждый рекурсивный вызов +1 и цепочка +1 останавливается, когда рекурсивные вызовы прекращаются.

Это также подсчитывает количество рекурсивных вызовов, но оно никогда не перестанет считать:

def keep_counting
  2 + keep_counting + keep_counting
end 

Answer 3

Я только добавил немного puts в ваш код, может быть, это помогает следовать логике лучше, чем я могу объяснить своим английским.

Итак, это подправленный код:

def rcall(num)
  if 10 == num
    rec = 0
    puts "rec = #{rec} ---- End of recursion"
    return rec
  end
  rec = rcall(num - 1)
  res = 1 + rec
  puts "rec = #{rec} \t\t res = i + rec = #{res}"
  res
end

Когда вы звоните на 15, например, вы получаете: rcall (15)

# rec = 0 ---- End of recursion
# rec = 0      res = i + rec = 1
# rec = 1      res = i + rec = 2
# rec = 2      res = i + rec = 3
# rec = 3      res = i + rec = 4
# rec = 4      res = i + rec = 5
# 5

Если вы звоните по номеру меньше 10, вы никогда не достигнете конца рекурсии, поэтому не возвращается значение для построения «стека вызовов» и возникает ошибка: stack level too deep (SystemStackError)

---

Другие языки поддерживают рекурсию, например Python. Здесь о знаменитой Фибоначчи ( Как написать последовательность Фибоначчи? ).

Я также хочу поделиться этим видео Computerphile о рекурсии на YouTube: https://youtu.be/Mv9NEXX1VHc

Answer 4

Рекурсия - это одна из тех вещей, о которых многие люди знают, но не так много людей могут описать ее напрасно (включая меня).Это общий метод программирования, который поддерживается несколькими языками, а не только Ruby.

Любой данный вызов сохраняет свое текущее состояние при повторном вызове метода, поскольку для продолжения ему требуется значение из этого значения.Только когда самый глубокий уровень возвращает значение (в данном случае 0), все разворачивается, так как предыдущие вызовы теперь имеют значения для работы (каждый добавляет 1).Вы получаете на 10 меньше, потому что вы используете 10 в качестве значения «завершения», по сути, пропуская все, что меньше, чем защитное сравнение (например, установите для сравнения 0 или отрицательное число).

В этом случаеЗащитный тест позволяет избежать ошибки «слишком большой уровень стека», поскольку нет ничего другого, что могло бы предотвратить рекурсию убегания - вы можете увидеть это, используя начальное значение, меньшее, чем сравнение, например, начиная с 5, когда сравнение для10.