Хвостовая рекурсия - PullRequest
Новая
       39

Хвостовая рекурсия

4 голосов
/ 19 октября 2011

Мы экспериментировали с параллельными коллекциями в Scala и хотели проверить, был ли упорядочен результат. Для этого я написал небольшую функцию в REPL, чтобы выполнить эту проверку в очень большом Списке, который мы создавали: 

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

Сбой в стеке переполнения (насколько уместен вопрос здесь!). Я ожидал, что это будет оптимизировано для хвоста. Что не так?

Ответы [ 4 ]

14 голосов
/ 19 октября 2011

isOrdered - это не последний вызов в вашем коде, оператор & есть. Попробуйте вместо этого: 

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}
8 голосов
/ 19 октября 2011

Ваш алгоритм неверен.Даже с улучшением @ Kim, isOrdered(List(4,3,5,4)) возвращает true.

Попробуйте: 

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

(также обновлено, чтобы знаки были правильными)

edit : мой предпочтительный макет будет таким: 

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

Быстрый способ, если производительность не проблема, будет 

def isOrdered(l: List[Int]) = l == l.sorted
2 голосов
/ 19 октября 2011

Он не может быть оптимизирован хвостом, потому что вы возвращаете это: 'x> y & isOrdered (tail)'. Это означает, что ему нужно будет хранить его в стеке.

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

1 голос
/ 19 октября 2011

Я думаю, что проблема в том, что вы используете битовый оператор и (&) в последнем случае.Поскольку среда выполнения должна знать значение вызова isOrdered, прежде чем она сможет оценить &, она не может оптимизировать функцию хвостом.(То есть после запуска isOrdered необходимо выполнить больше кода - побитовую операцию - и.)

Использование оператора && или оператора if может помочь.

...