user2300867 - 1 year ago 100
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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download