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

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

0 голосов
/ 04 июня 2019

Обучение 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)
}

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

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

Ответы [ 2 ]

2 голосов
/ 04 июня 2019

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

@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)
  }
}
0 голосов
/ 04 июня 2019

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

 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!

Stack overflow error in tail-recursive method

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

ИтакЯ пошел дальше и изменил сигнатуру factorialTailRec/2 на: 

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

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

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

...