Хвостовая рекурсия и вызов по имени/значению

Изучение Scala и функционального программирования в целом. В следующей реализации факториала с хвостовой рекурсией:

def factorialTailRec(n: Int) : Int = {

    @tailrec
    def factorialRec(n: Int, f: => Int): Int = {
      if (n == 0) f else factorialRec(n - 1, n * f)
    }

    factorialRec(n, 1)
}

Интересно, есть ли какая-то польза от того, что второй параметр вызывается по value по сравнению с вызовом по name (как я сделал). В первом случае каждый кадр стека обременен продуктом. Во втором случае, если я правильно понимаю, вся цепочка произведений будет перенесена в случай if ( n== 0) на n кадре стека, поэтому нам все равно придется выполнять то же количество умножений. К сожалению, это не произведение формы a^n, которое можно вычислить за log_2n шагов путем многократного возведения в квадрат, а произведение членов, каждый раз отличающихся на 1. Поэтому я не вижу никакого возможного способа оптимизации конечного продукта: он все равно потребует умножения O(n) членов.

Это правильно? Эквивалентен ли здесь вызов по значению вызову по имени с точки зрения сложности?


scala tail-recursion callbyname call-by-value
person Jason    schedule 04.06.2019    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

@tailrec
def factorialTailRec(n: Int, f: => Int): Int = {
  if (n == 0) {
    val fEvaluated = f
    fEvaluated
  } else {
    val fEvaluated = f // <-- here we are going deeper into stack. 
    factorialTailRec(n - 1, n * fEvaluated)
  }
}
person simpadjo    schedule 04.06.2019
comment
Ха! Угадайте, что произошло, когда я заменил val на def. Этот язык удивителен. Спасибо. - person Jason; 04.06.2019
comment
Я думаю, это начало работать, не так ли? В любом случае, я настоятельно рекомендую использовать не более одной замечательной возможности scala одновременно. Обычно удивительности не суммируются, как в вашем случае :) - person simpadjo; 04.06.2019
comment
Да, это так. Просто в тот момент я вспомнил, что val оценивает, тогда как def... определяетимя и ждет, пока оно будет вызвано. Я ожидаю, что lazy val здесь будет иметь тот же эффект, что и def. Я проведу расследование еще раз перед компьютером. Вы правы насчет моего чрезмерного энтузиазма: преждевременная оптимизация, корень всех зол и т. д. - person Jason; 04.06.2019

arrow_upward
0
arrow_downward

Путем экспериментов я обнаружил, что с формализмом вызова по имени метод становится... не хвостовой рекурсией! Я сделал этот пример кода для сравнения факториала с хвостовой рекурсией и факториала без хвостовой рекурсии:

 package example

 import scala.annotation.tailrec

 object Factorial extends App {

  val ITERS = 100000

  def factorialTailRec(n: Int) : Int = {
    @tailrec
    def factorialTailRec(n: Int, f: => Int): Int = {
      if (n == 0) f else factorialTailRec(n - 1, n * f)
    }
    factorialTailRec(n, 1)
  }

  for(i <-1 to ITERS) println("factorialTailRec(" + i + ") = " + factorialTailRec(i))


  def factorial(n:Int) : Int = {
    if(n == 0) 1 else n * factorial(n-1)
  }

  for(i <-1 to ITERS) println("factorial(" + i + ") = " + factorial(i))

}

Обратите внимание, что внутренняя функция tailRec вызывает второй аргумент по имени. для которых аннотация @tailRec по-прежнему НЕ выдает ошибку времени компиляции!

Я играл с разными значениями переменной ITERS, и для значения 100 000 я получаю... StackOverflowError!

Ошибка переполнения стека в методе хвостовой рекурсии

(Результат равен нулю из-за переполнения Int.)

Поэтому я пошел дальше и изменил подпись factorialTailRec/2 на:

def factorialTailRec(n: Int, f: Int): Int

то есть вызов по значению для аргумента f. На этот раз часть main, которая запускает factorialTailRec, завершается абсолютно нормально, в то время как, конечно, factorial/1 падает с тем же самым целым числом.

Очень, очень интересно. Кажется, что вызов по имени в этой ситуации поддерживает кадры стека из-за необходимости вычисления самих продуктов на всем пути обратно к цепочке вызовов.

person Jason    schedule 04.06.2019
comment
Ваша функция — tailrec. Дело в том, что он строит не-tailrec-функцию (путем tailrec), которая в конце вычисляется, а последняя разбивает стек. Параметр по имени похож на функцию без аргументов. - person Luis Miguel Mejía Suárez; 04.06.2019
comment
Боюсь, я не совсем понимаю, что вы имеете в виду, когда говорите о построении функции, отличной от tailrec, с помощью tailrec. Мое интуитивное представление о том, что здесь происходит, заключается в том, что в точке возврата (базовый случай хвостовой рекурсии) мы должны оценить произведение из n членов. Если это накладные расходы, я бы понял. К сожалению, вывод терминала касается, строго, StackOverflowError, что заставляет меня думать, что это не может быть tailrec! - person Jason; 04.06.2019
comment
@Jason: factorialTailRec является хвостовой рекурсией. Однако создаваемая им анонимная функция (которая, по сути, является параметром по имени) таковым не является. - person Jörg W Mittag; 04.06.2019
comment
@ Джейсон, вы правы, что в конце программа оценивает произведение n членов. Дело в том, что этот продукт построен как нехвостовая рекурсивная анонимная функция, как сказал Йорг В. Миттаг. Когда вы используете параметры по значению, это должно работать, потому что вы будете создавать не функцию, а значение. - person Luis Miguel Mejía Suárez; 04.06.2019
comment
Понятно, все. Большое спасибо. Это обобщает, верно? Невозможно иметь функцию хвостовой рекурсии, если любой из ее аргументов вызывается по имени. - person Jason; 04.06.2019