Recursion and Tail Recursion in Scala

Table of contents

Reading Time: 4 minutes

Introduction:

Recursion is quite common in the programming world. If you don’t know recursion, it means, solving a problem by breaking it into smaller sub-problems until you solve it trivially. You can easily spot recursion if you see a method calling itself with a smaller subset of input. Recursion and immutability are corner zone of functional programming. As we have seen earlier, while using loops, we tend to use vars that either accumulate results or tries the loop. However, we can use recursion to get around with these vars and convert these vars into Val.

We usually do not observe much recursion in object-oriented programming but recursion is quite common in functional programming. Recursion provides a natural way to describe many algorithms and an important point to notice here is that while we use recursion in scala, it is mandatory to provide a return type as it is difficult for the compiler to reduce it.

Let us see an example of recursion. We will try to find out the greatest common factor of two numbers using recursion. I will declare a method gcd that will take two integers and will return one integer. You will have to carefully write the condition at which your recursion should exit otherwise you will be in an infinite loop.

Let’s test some methods with some input.

scala > def gcd (a:Int, b:Int):Int = {
     | if(b == 0) a
     | else gcd (b, a%b)
     | }
def gcd (a: Int, b: Int): Int

scala > gcd(12,18)
val res0: Int = 6

Problems on Recursion:

Recursion involves building up on a call stack which can be expensive, there is one major problem with plain recursion that it may blow up your stack if you are not careful. Let me explain it with an example.

Consider a small example of the sum of digits. The method sum will try to sum up all the numbers till the input. Carefully observer how we reduce a number every time and add it to the result. Here, whenever we call sum again, we will leave input Val num on the stack. Thus, exhausting a little bit of memory every time.

scala> def sum(num:Int):Int = {
     | if (num ==1 ) 1
     | else sum(num-1) + num
     | }
def sum(num: Int): Int

Let us try to rum some sample input

scala> sum(999)
val res0: Int = 499500

And it goes fine. Now, let us add one more 9 to it.

scala> sum(9999)
java.lang.StackOverflowError

  at sum(<console>:2)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
  at sum(<console>:3)
   .
   .
   .
   .

And you will see, it has blown up the Stack.

Tail Recursion:

In order to avoid such a problem, we should use tail recursion. So the first question is, what is tail recursion. If the recursive call is the last operation performed by the function and no operation or data needs to be saved when the function returns, it is called tail recursion. If there is nothing on the stack frame, the compiler can reuse the stack frame and convert it into a loop. Let us understand by an example.

In order to convert recursion to tail recursion, we need to pass another input to our method that will keep track of the sum whenever we are down to 1 will return this result. Carefully observe this time, now, we are not leaving any residue over the stack.

scala> def sum(num:Int, res:Int): Int= {
     | if (num == 1) res
     | else sum(num-1, res+num)
     | }
def sum(num: Int, res: Int): Int

Now let us run some previous inputs, which we have given in the previous code, and add some more values out of curiosity.

scala> sum(99999,1)
val res2: Int = 704982704

scala> sum(999999,1)
val res3: Int = 1783293664

scala> sum(9999999,1)
val res4: Int = -2014260032

@tailrec Annotation:

So far so good. Now this was the small example of recursion and we can look at it and determine if the call was tail-recursive or not, but in real-life projects, recursions are not that easy. So, how would you tell, recursion is tail-recursive. There is an easy way in scala to check if the calls are tail-recursive and that is to use tail recursive annotation.

Once you put that annotation over your method calls, scala will check your method if it is tail-recursive. If it is not, then scala will throw you a compile-time error. In order to use this annotation, we need to import scala. annotation package.

Let us see an example. Firstly, import scala.annotation will put tail recursion over some method that is not tail-recursive.

scala> import scala.annotation._
import scala.annotation._

scala> @tailrec
     | def sum(num:Int):Int = {
     | if (num == 1) 1
     | else sum(num-1) + num
     | }
                      
On line 4: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position

And you can see straight away scala has thrown us a compilation error. Let us try by putting the tail recursion annotation over the method that we claim is tail-recursive.

scala> import scala.annotation._
import scala.annotation._

scala> @tailrec
     | def sum(num:Int, res:Int):Int={
     | if (num == 1) res
     | else sum(num-1, res+num)
     | }
def sum(num: Int, res: Int): Int

And this time, it is a success. Let us check it by giving some values.

scala> sum(999,1)
val res0: Int = 499500

Conclusion:

This topic will be used in plenty of useful places in your code. Recursion is an important concept and hard to master. So, I would say, keep practicing. That’s all basic, I have in my mind as of now related to recursion and tail recursion best practices, which could be understood by any beginner level programmer. The language does not matter. You can write in any language you want to write.

So, focus on the logic. If you found anything missing or you do not relate to my view on any point, drop me a comment. I will be happy to discuss. For more blogs, click here