Recursion in scala in a simple way

Reading Time: 4 minutes

What is Recursion?

It is the technique of making a function call itself directly or indirectly and the corresponding function is called a recursive function. This technique provides a way to break complicated problems down into simple problems which are easier to solve. Recursion may be a bit difficult to understand and it can take some time to get your head around how it works

What is a base case in recursion? 

In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems. Let us take an example to understand this.

In the above example, the base case for n < = 1 is defined and a larger value of a number can be solved by converting to a smaller one till the base case is reached.

Why StackOverflow error occurs in recursion? 

If the base case is not reached or not defined or if the recursion depth is too deep, then the StackOverflow problem may arise. Let us take an example to understand this.

If factorial(25) is called, the value of n will be 25, 24, 23, 22, and so on but the number will never reach 500. So, the base case is not reached. If the memory is exhausted by these functions on the stack, it will cause a StackOverflow error. 

Simple Recursion

The following example shows stack Recursion. In the example below, we will see what function will do at each stage of the recursion.

The output of the above code as follows

Here we can see how the compiler interacts with the code. The compiler stops where it makes the next recursion calls. When the base case is reached, the function returns its value to the function by whom it is called and the process continues. The else blocks then complete back to the original value for n and print the result.

What is the trouble with the above approach?

The JVM keeps all the calls in its internal stack. The internal stack has limited memory. So if we try to find the value of factorial(10000). This will cause a Stack Overflow error because the recursion depth is too deep for the JVM to handle.

Tail Recursion

To overcome the above trouble we use trail recursion. If you have a recursive function that calls itself as its last action, then you can reuse the stack frame of that function. This is called tail recursion. Let us write the factorial function in another way. This time we will use tail recursion.

In the above example, we have used an auxiliary function “helper” and the make tail-recursive. We have made the helper function tail-recursive using a @tailrec annotation. Import scala.annotation.tailrec to use @tailrec.

Let us understand each step of the recursion when we call factorial(5).

• The initial value of n is 5 and factorial function calls the helper function as helper (5,1)
• This goes into the else block and calls helper(4, 5*1)
• Again it goes into the else block and calls helper(3, 4*5*1)
• Again it goes into the else block and calls helper(2, 3*4*5*1)
• Then again with helper(1, 2*3*4*5*1)
• And finally, the base case is reached which return the value of accumulator which is 2*3*4*5*1

Now if we try to find factorial(10000), it will return the value without StackOverflow error. Because we wrote helper function as the last expression of the code path. This allows Scala to preserve the same stack frame through the recursive calls, instead of using additional frames for each call.

Conclusion

In this post, we have learned what is recursion, how it works, StackOverflow error, how to solve StackOverflow error using tail recursion.

References

• https://www.scala-exercises.org/scala_tutorial/tail_recursion

If you find this article interesting, please check out our other articles.