user2300867 - 9 days ago 5x
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
}

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 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.

Source (Stackoverflow)