Hello Everyone, I am new in this community. Can anyone tell me what the process of tail recursive in scala? I am confused to understand it . I also want to know the specific work of this process. I am preparing some scala interview questions for my upcoming interview. Can anyone suggest me some tips for scala profile?
Tail Recursive in Scala
Yes, I also support you need to use tail recursion.
A tail-recursive function is just a function whose very last action is a call to itself. When you write your recursive function in this way, the Scala compiler can optimize the resulting JVM bytecode so that the function requires only one stack frame — as opposed to one stack frame for each level of recursion!
0 Likes
Eumaeus
#5
This is from back in May, and Stack Overflow might be a better forum, but here goes. What follows is a near-plagiarism of Alvin Alexander on Scala’s Tail Recursion.
Recursion is just “a function calls itself”. There are several ways to do this. Some are better than others for certain tasks. Let’s say you are writing a sum function, where sum(3) == 6 (that is, for 3, 1+2+3. You could do this:
val myNumber: Long = 10
def badSum(n: Long): Long = {
if (n == 0) n // return 'n'
else n + badSum(n - 1) // call this same function. Recursion!
}
val sumOfMyNumber: Long = badSum(myNumber)
This works, and it is good Scala. Nothing but immutable values here. The badSum function it entirely self-contained, but it will fail for big numbers. Try the code above, but instead of 10, use 20000.
If myNumber is 0, the function just returns the answer 0. But otherwise, it recurses. That is, it calls itself with a new value n.
To understand why this one will fail with large numbers, we can unpack it. The compiler will expand function calls to their actual values. So let’s see what the compiler expands the line else n + badSum(n - 1) to…
badSum(5)
5 + badSum(4)
5 + (4 + badSum(3)
5 + (4 + (3 + badSum(2))
5 + (5 + (3 + (2 + badSum(1)))
5 + (5 + (3 + (2 + (1 + 0)))) => 15
This gets the job done, but the computer has to hold all of that in memory—it drills all the way down, first, then has to do the summing from the inside out.
Scala provides an alternative, tail-recursion. It is complicated, but the short version is that if a function calls-itself as the last thing it does, then Scala, using immutable values, can simply throw away any previous data and work with new copies of it. It looks like thins:
def goodSum(n: Long): Long = {
@tailrec
def sumTailRec(runningTotal: Long, n: Long): Long = {
if (n == 0) runningTotal
else sumTailRec(n + runningTotal, n - 1)
}
sumTailRec(0, n)
}
The parameter named runningTotal is an example of what is called an accumulator. Calling goodSum(15) will look like this as it is processed…
runningTotal(0, 5)
runningTotal(5, 4)
runningTotal(9, 3)
runningTotal(12, 2)
runningTotal(14, 1)
runningTotal(15, 0) => returns runningTotal == 15
There are still five recursion events, but they happen one after another, and once one has taken place, the computer can forget about it.
These two won’t make much difference when summing 5. But the latter can sum 200,000, while the former will crash your computer trying.
Maybe this helps?
0 Likes