Попытка закрепить понимание хвостовой рекурсии в Scala

Question

Я готовлюсь к экзамену в Scala и пытаюсь выяснить вопрос, который я пропустил.Я понимаю хвостовую рекурсию как «последний вызов сам по себе», но меня смущает различие между некоторыми из этих фрагментов кода.Почему этот хвост считается рекурсивным,

def f(x: Int): Int = {
    if (x % 2 == 0) {1} 
    else {f(x + 1)}

, но это не так?

def f(x: Int): Int = {
    if (x % 2 == 0) {1} 
    else {1 + f(x + 1)}

Что именно делает добавление 1 к функции, ограничивающее ее рекурсивность?Извините, если это глупый вопрос, я не вижу влияния, которое оказывает число, и хочу укрепить мое понимание.Любые другие указатели на полную способность идентифицировать хвостовую рекурсию тоже были бы великолепны!

Answer 1

Ваше понимание не совсем верно.Хвостовая рекурсия означает не «последний вызов сам по себе», а «последний вызов сам по себе».То есть хвостовой рекурсивный вызов должен быть последним действием, выполняемым функцией.Это должен быть «хвост» списка действий, которые функция выполняет над этим путем кода.(Конечно, должен быть путь к коду, который не включает рекурсивный вызов).

Также важно подумать о том, как оцениваются значения в выражении, а не в порядке их появления в коде.,Это выражение

1 + f(x + 1)

выполняется в следующем порядке:

tmp1 = x + 1
tmp2 = f(tmp1)
res = 1 + tmp2

или, альтернативно,

add(1, f(add(x, 1))

Записано так, как вы можете видеть, что вызов f сопровождается другим действием, заключительным + / add.Поскольку рекурсивный вызов не является последним действием, он не является хвостовой рекурсией.

Answer 2

Часто помогает явно записать все в нотации вызова функции:

def f(x: Int): Int =
  if (==(%(x, 2), 0) 1 
  else f(+(x, 1))

def f(x: Int): Int =
  if (==(%(x, 2), 0) 1 
  else +(1, f(+(x, 1)))

Можете ли вы определить, почему во втором примере последний вызов не является f?

Answer 3

Во втором фрагменте последний вызов - это не "сам по себе", а +.Вы должны сначала получить результат от f(x+1), а , а затем добавить 1 к нему, прежде чем вернуться.Таким образом, текущий кадр должен оставаться в стеке для вызова f(x+1).

И наоборот, в первом фрагменте ничего не остается делать после вызова f(x+1), поскольку его результат становится возвращаемым значением.Таким образом, компилятор может удалить текущий кадр из стека до совершения вызова, так что результат вызова f(x+1) будет возвращен непосредственно вызывающей стороне f(x).