user2300867 - 4 months ago 62

Scala Question

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.