Stack recursion call and Tail Recursion in Scala
Recursion is the process of defining something in terms of itself,In any programming language method calling itself until certain condition is call Recursive method, so we are familiar with recursion now,and we will further dive on type of recursive function
Stack recursion call
So Stack is data structure where operation are performed in Last in first out order,so Stack recursion call is where function before executed are stored in stack and then executed in the stack order,so let see with small example of factorial of number
def fact(n: Int): BigInt = {
if (n > 0) n * fact(n - 1)
else 1
}
fact(10);
so during runtime stack memory is allocated,and statements are pushed to stack before execution as shown in the image below,and when all the statements are pushed the function starts executing,and final result is retuned when stack become empty,in these type of recurssion we often end up with stack over flow exception when stack memory is filled up.
Tail Recursion program
concept of recursion remains same, but we modify our program a bit so the statements are not pushed to stack, instead works like iterator,
def factorial(n: Int, acc: BigInt = 1): BigInt = {
if (n <= 0) acc
else {
factorial(n - 1, acc * n)
}
}
variable acc (accumulator) will hold product when n reaches zero product is returned,so we avoid stack overflow exception during runtime and @tailrec
annotation is also added to suggest the type recursive function to compiler to ignore warnings