Хвостовая рекурсивная функция (проблемы с Coursera)

Я слежу за курсом функционального программирования на Scala на Coursera, чтобы выучить язык.

Они ввели понятие хвостовых рекурсивных функций и определили их в основном как функцию, которая заканчивается вызовом самой себя. Но затем они показывают это как отработанный пример:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

Если я аннотирую сумму с помощью @tailrec, я получаю сообщение об ошибке, потому что IDE (IntelliJ) не считает ее хвостовой рекурсивной.

Сумма называется хвостовой рекурсивной здесь, или "цикл" внутренней реализации в данном случае считается хвостовой рекурсией?


syntax scala higher-order-functions tail-recursion
person John Humphreys    schedule 21.06.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Ты прав. sum необходимо вызвать себя, иначе Scala будет жаловаться на:

@tailrec annotated method contains no recursive calls

Если вы сообщите компилятору, где именно он находится, переместив @tailrec туда, где находится хвостовая рекурсия:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  @tailrec def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

Тогда компилятор будет удовлетворен оптимизацией хвостовой рекурсии.

person bjfletcher    schedule 21.06.2015

arrow_upward
1
arrow_downward

Внутренний метод loop является хвостовым рекурсивным, метод sum вообще не рекурсивен. Следовательно, вы должны аннотировать loop с помощью @tailrec.

Перемещение loop во внешний осциллограф может помочь визуализировать происходящее:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
    loop(a, 0)
}

def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
}

Как видите, sum - это просто общедоступная точка входа для loop.

(Обратите внимание, что приведенный выше код не будет компилироваться, потому что loop больше не закрывается через b или f, но суть вы поняли.)

person dcastro    schedule 21.06.2015