Scala Tutorials Part #25 - Recursion


Recursion

Recursion is a fundamental concept in many programming languages and it is important to understand how it works in Scala and its significance in the language.

This is part 25 of the Scala tutorial series. Check here for the full series.

Index

Introduction

Recursion

Scala has full support for functional programming and recursion is important to write functional code.

Let’s take a simple factorial example.

  def factorial(x:Int) : Int = {

if(x==0) 1 else x * factorial(x-1)

}

This piece of code is not tail-recursive, i.e the last part of the function creates additional stack frames per call. The moment you get pretty deep in the call stack then you end up the famous StackOverflowError

Stack overflow

Let’s modify the above code to work on BigInt instead of Int so that we can simulate the error.

 def factorial(x:BigInt) : BigInt = {

if(x==0) 1 else x * factorial(x-1)

}

If we call this with a ridiculously high value such as factorial(10000) then,

Exception in thread "main" java.lang.StackOverflowError
at scala.math.BigInt$.apply(BigInt.scala:49)
at scala.math.BigInt$.long2bigInt(BigInt.scala:101)
at scala.math.BigInt.isValidLong(BigInt.scala:131)
at scala.math.BigInt.equals(BigInt.scala:125)
at scala.runtime.BoxesRunTime.equalsNumNum(BoxesRunTime.java:168)
at scala.runtime.BoxesRunTime.equalsNumObject(BoxesRunTime.java:140)

The Stack space is a limited memory area, and this exception is unrecoverable and generally results in the application crashing. There are plenty of resources on the web that goes into detail on explaining of how stack overflow occurs internally, so I am not going to bother explaining.

Tail recursion

Xkcd Functional

The common way to overcome a stack overflow error is to write a tail recursive version. Developers will usually resort to loop constructs but its better modeled with recursion when you are writing pure functions which is referentially transparent.

  def factorial(x:BigInt) : BigInt = {

def internal (acc:BigInt,n:BigInt) : BigInt = {
if (n == 0) acc
else internal(acc * n, n - 1)
}

internal(1,x)

}

This version should run the factorial(10000) without any issue. In fact, it can run even higher numbers until we hit either a type limit or memory issue. We create another internal helper function which acts as an accumulator which uses n-1 as the last call which is tail recursive. Tail recursion is the functional counterpart of iteration and hence it is always necessary to do tail call optimization when the values could get large.

Intellij is always helpful in telling us whether the function is tail recursive or not.

Recursive

Tail recursive

I am not going to explain on converting regular functions into its tail recursive versions, that is a topic for another tutorial.

Tailrec annotation

Apart from the IDE helping you out, the Scala compiler has an annotation that throws an error if the function is not tail recursive.

@tailrec
def factorial(x:BigInt) : BigInt = {

if(x==0) 1 else x * factorial(x-1)

}

Error is thrown at compile time.

Tail rec error

In this case, the compiler is not able to optimize into a loop. The annotation works as intended on the inner recursive function.

Tail rec success

It is important to understand what the @tailrec annotation actually means. Some important notes below.

You don’t annotate methods that can be optimized. You annotate methods that must be optimized, so that you will get a compile error, when they can’t be optimized.

It is more of a documentation to the developers. Many functional languages such as Haskell perform automatic tail call optimization (with conditions applied). Scala cannot do this due to the limitation with the JVM.

Conclusion

Recursion is interesting because it is very important for functional programming languages to write good functional code. There are some limitations in the JVM due to which there is no automatic tail call optimization. But the @tailrec annotation comes in handy in such situations. Certain algorithms such as tree traversals, search are naturally recursive in nature.

Hopefully this article gave you a good overview of recursion. They are not meant for replacing loops entirely, but with modern JVMs they should work similar to loops in terms of performance. It is important to consult the documentation for your VM and also don’t forget to test everything.


Tagged Under


Scala


Search this website...




Keeping up with blogs...

I blog occasionally and mostly write about Software engineering and the likes. If you are interested in keeping up with new blog posts, you should follow me on twitter where I usually tweet when I publish them. You can also use the RSS feed , or even subscribe via email below.

Feedio Subscribe


Share & Like

If you like this post, then you can either share/discuss/vote up on the below sites.



Thoughts ...

Please feel free to share your comments below for discussion

Blog comments powered by Disqus