Scala Recursion

Question

Как написать функцию ниже в регулярной рекурсии и рекурсии хвоста.

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = { 
    var satisfies = 0 
    for (i <- 0 until x.length) { 
     if (test(x(i))) satisfies += 1 
    } 
    satisfies == x.length 
    } 

Answer 1

Вот базовая рекурсивная версия.

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = 
    if (x.isEmpty) true 
    else if(test(x.head)) satisfiesAllIt(x.tail, test) && true 
    else false 

Вот хвостовая рекурсивная версия.

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = 
    if (x.isEmpty) true 
    else if(test(x.head)) satisfiesAllIt(x.tail, test) 
    else false 

И это то, что вы делаете после изучения стандартной библиотеки.

def satisfiesAllIt(x: List[_], test: Any => Boolean): Boolean = x.forall(test) 

---

@The Архетипический Павел делает хорошую точку (как он часто делает), и предложил альтернативу.

// basic recursive 
def satisfiesAllA(x: List[Any], test: Any => Boolean): Boolean = 
    x.isEmpty || satisfiesAllA(x.tail, test) && test(x.head) 

// tail recursive 
def satisfiesAllB(x: List[Any], test: Any => Boolean): Boolean = 
    x.isEmpty || test(x.head) && satisfiesAllB(x.tail, test) 

То, что мы все танцевали вокруг, фактически не указывая его, является определяющим различием между основной и хвостовой рекурсией: если есть больше «работа», чтобы сделать после того, как рекурсивные возвраты вызова (расчеты/оценок/etc.), то это не хвост рекурсивный.

Answer 2

Вот хвостовая рекурсивная версия satisfiesAllIt. Идея состоит в том, чтобы вызывать функцию рекурсивно, пока список не закончится, и верните false, если тест завершился с ошибкой.

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = xs match { 
    case Nil => true 
    case x :: xs => 
    if (test(x)) satisfiesAllIt(xs, test) else false 
}