Хвостовая рекурсия и возврат заявления в Scala

Question

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

В любом случае, я думалчто-то вроде этого:

def simpledb_update(name: String, metadata: Map[String, String]) = {

  def inner_update(attempt: int): Unit = {
    try {
      db(config("simpledb_db")) += (name, metadata)
      return
    } catch {
      case e =>
        if (attempt >= 6) {
          AUlog(name + ": SimpleDB Failed")
          return
        }
    }
    inner_update(attempt+1)
  }

    inner_update(0)
}

Или

def simpledb_update(name: String, metadata: Map[String, String]) {

  def inner_update(attempt: int): Unit = {
    try {
      db(config("simpledb_db")) += (name, metadata)
    } catch {
      //Do I need the pattern match, since I don't
      // care what exception is thrown???
      if (attempt >= 6) {
        AUlog(name + ": SimpleDB Failed")
      } else {
        inner_update(attempt+1)
      }
    }
  }

  inner_update(0)
}

Является ли вторая реализация все еще хвостовой рекурсивной (первая ???).Я все еще немного запутался, когда функция рекурсивна, а когда нет.

Answer 1

Да, оба примера все еще хвостовой рекурсии, сначала вы выполняете проверку / обработку, а рекурсивный вызов - последний.

Файл Jargon выражается кратко: Хвостовая рекурсия (n): Если вам это уже не надоело, посмотрите рекурсию хвоста.

Answer 2

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

Answer 3

Хвостовая рекурсия проста для понимания - если последнее выражение из всех путей кода функции F является просто вызовом функции, то оно является хвостовой рекурсией.Но зависит ли это от рекурсивной оптимизации компилятора Scala - зависит.Тот факт, что JVM не использует TCO, означает, что компилятор scala творит чудеса.

И причина, по которой scalac может не оптимизироваться, связана с полиморфизмом.Если функцию можно переопределить в подклассе, то ее нельзя оптимизировать с помощью скалака.

@ Timo Rantalaiho, использование аннотации tailrec является наиболее безопасным способом проверки возможности выполнения TCO.