user2300867 user2300867 - 1 month ago 28
Scala Question

Scala Recursion

How could I write function below in regular Recursion and Tail Recursion.

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

Here's a basic recursive version.

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

Here's a tail recursive version.

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

And this is what you do after you've studied the Standard Library.

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

@The Archetypal Paul makes a good point (as he often does) and has offered an alternative.

// 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)

What we're all dancing around, without actually pointing it out, is the defining difference between basic and tail recursion: if there's any more "work" to be done after the recursive call returns (calculations/evaluations/etc.) then it is not tail recursive.