Преобразовать сферную функцию в хвостовую рекурсивную функцию - PullRequest
Новая
       21

Преобразовать сферную функцию в хвостовую рекурсивную функцию

1 голос
/ 14 июня 2019

Я реализовал функцию Sphere (берет список элементов, возводит в квадрат каждый элемент и возвращает сумму) в Scala. Я хочу преобразовать эту функцию в хвостовую рекурсию. Мой код здесь 

def Sphere(list: List[Double]): Double = {
  val power = list.map(math.pow(_, 2))
  power.reduce(_+_)
}

Ответы [ 3 ]

5 голосов
/ 14 июня 2019

Похоже: 

  @tailrec
  def Sphere(list: List[Double], result: Double = 0): Double = list match {
    case Nil => result
    case x::xs => Sphere(xs, result + math.pow(x, 2))
  }

  println(Sphere(List(1,3,4,5)))

С @tailrec вы убедитесь, что он действительно хвостовой рекурсии (компиляция не удастся).

Важным является:

  • что последний вызов для себя
  • что он имеет промежуточный результат в списке параметров
  • x является главой списка, в котором вы производите вычисления
  • xs - остальная часть списка (хвост ), в который вы добавляете рекурсивную функцию, до тех пор, пока список не станет пустым> Nil.
4 голосов
/ 14 июня 2019

Если вы хотите сохранить ту же сигнатуру функции, вам нужно использовать вложенную рекурсивную функцию: 

def Sphere(list: List[Double]): Double = {
  @annotation.tailrec
  def loop(rem: List[Double], res: Double): Double =
    rem match {
      case hd :: tail => loop(tail, res + hd*hd)
      case _ => res
    }

  loop(list, 0)
}

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

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

В дополнение к ответам выше, если вы используете foldLeft, он уже оптимизирован для хвостового вызова 

def Sphere(list: List[Double]): Double = {
    list.foldLeft(0.0)((res, elem) => res + elem * elem)
}

Лучше использовать версии библиотеки и не добавлять дополнительную проверку (@tailrec) для компилятора, когда материал доступен.

** foldLeft аналогичен ReduLeft, за исключением того, что он принимает дополнительное начальное значение в качестве аргумента и не выдает исключение, когда коллекция пуста.

** Реальная реализация foldLeft заканчивается использованием whileцикл по соображениям производительности, но опять же, это преимущество хвостовой рекурсии, сделайте его таким же быстрым, как цикл.

...