I know while using Loops, mutability comes into picture and keep things difficult to have a track of. But is it just because of mutability that recursion is considered over loops in Scala?

Additionally I understand that tail recursion doesn't add to your call stack but not all the problems can be solved using tail Recursion right? What about using an Accumulator based approach which also seems to be sufficient enough for avoiding stack overflow cases? What can be more performant between tail Recursion and Accumulator based Recursion Approach?

In short, I have two questions:

1. Since tail recursion cannot be used to solve all loop problems (or can it?) isn't looping the better or the only solution for some specific use cases?
2. What is the difference between tail recursion and accumulator based recursion and which is more performant based on the space complexity and call stack occupied?

Edit 1:

Example of a non tail recursive function (which uses an intermediate tail recursive function) that is converted in Accumulator based recursion (Factorial Function):

Without Accumulator:

def factorial(n: Int): Int = {
  if (n <= 1) 1
  else n * factorial(n - 1)
}

With Accumulator:

def tailRecFactorial(n: Int): BigInt = {
    @tailrec
    def factorialHelper(x: Int, accumulator: BigInt): BigInt = {
      if (x <= 1) accumulator
      else factorialHelper(x - 1, x * accumulator)
    }
    factorialHelper(n, 1)
  }

CodePudding user response：

Scala is a functional language, and functional code is generally considered better than non-functional code. The objection to while is that it relies on a value changing during the iteration and therefore cannot be functional.

To answer the specific questions:

1. Any loop can be expressed as a pure tail recursive function, but it can get very hairy working out what state to pass to the recursive call.

2. "tail recursion" and "accumulator based recursion" are not mutually exclusive. A tail recursive function is any function that calls itself as the last action on at least one of the code paths. Accumulator based recursion simply means passing a partial result to the recursive call as a way of converting a non-tail-recursive function to a tail recursive function.

CodePudding user response：

Well, first of all, not sure what you mean by accumulator-based recursion?

Second, Scala only has while loop, and all while loops can be expressed in terms of (tail) recursion; AFAIK.

Third, yeah, we prefer recursion over while to avoid mutability.
But still, recursion itself is too low level. In general, you should prefer higher-order combinators like map or foldLeft

Fourth, while mutability is contained in a single method is OK, is usually better to be consistent everywhere and keep everything immutable (unless you have very good reasons for the otherwise) than randomly mix mutability with immutability just because.