Skip to main content

Tail recursion in Scala



Today I learned that tail recursion optimization can really solve the classic problem of stack overflow in recursive functions that depend on data size


this I saw by writing a simple sum function in Scala that sums up a list


val x = (1 to 3).toList

// simple recursive function
def sum(x: List[Int]): Int = {
   if (x.isEmpty) 0
  else x.head + sum(x.tail)
}


ok so far so good, this works, and return 6 for the simple list of size 3.

But change the 3 to 300000 and you will see a stackOverFlow in the Scala workspace (you save the workspace and Scala will re compute). This is because a new frame is added to the stack for each recursive call and soon that exceeds the stack limit.



How do you solve this?

Tail recursion comes to the rescue. The term applies to functions whose last call is actually a self call, without any other computations. Scala compiler will internally then convert such functions into a while loop with goto, instead of pure recursion, hence avoiding the stack overflow issue


you can see this in action if you change the method to

  def sumX(x: List[Int], seed: Int): Int = {
     if (x.isEmpty) seed
     else sumX(x.tail, seed + x.head)
  }


Now you can call

sumX(x, 0) and this will work no matter how large the list is. The initial seed value should be 0 of course.



But this is an odd looking api, so let's fix it up by wrapping up this into an internal function so we don't have to provide the initial seed


def sum(x: List[Int]): Int = {
  def sumX(x: List[Int], seed: Int): Int = {
     if (x.isEmpty) seed
     else sumX(x.tail, seed + x.head)
  }
  sumX(x, 0)
  }           



Much better, now call sum(x) and you will get what you want.

Happy Scala coding! I love this language



Comments

Post a Comment

Popular posts from this blog

Authenticating Spring Boot based application against secure LDAP/AD server

Authenticating against an Active Directory setup is quite common in organizations using Spring Boot / Spring Security can be a pain if you don't know exactly the requirements. I needed to add auth in my web app and secure some but not all endpoints of the application. My story was, I needed Spring security to authenticate against my company LDAP server which uses Active Directory I started by using the standard LDAP guide such as this which are all over the Internet, https://spring.io/guides/gs/authenticating-ldap/ and was able to setup the basic framework However, only test level LDAP auth was working for me, when I tried to auth against the company LDAP secure server, I had to resolve a few issues After 1 week and working with several devs at the company, I finally found why it was not working and the fix was easy Since I spent a week or so resolving this, I wanted to write this up in case someone finds this useful. Here is what I did (it was easy until the fourth ...
Post a Comment
Read more

Unit testing code that uses environment variables and system properties with fakes

I did not exactly learn this today, but I am sharing it as I have found it extremely useful when unit testing code that depends on environment or system property settings. While I am using Java as an example, the general concepts apply any where. Problem : You have a piece of code you are unit testing that uses settings from env variables or system properties passed to the VM (System.getProperty), but you don't want the tests to be affected by the 'real' environment or system properties in the VM. So, your unit tests should not get different results or fail when the real environment changes. Solution : There are several. But the most straightforward is to use a mocking library to mock out the environment or fake it out, whatever your prefer. You can create a fake using a library like EasyMock, PowerMock etc. This I won't discuss in this post, since there are numerous articles for that. Or you can write a simple class that acts as a proxy, using the proxy pattern...
Post a Comment
Read more

Using custom conditional logic to enable/disable Spring components

If you have a Spring component and you don't want it to load, you can use Spring's predefined conditionals as much as possible. For example, @Component   @ConditionalOnNotWebApplication   public class SchedulerEntryPoint implements ApplicationRunner { ...  } This will not load your component when running in non web application mode. Such as you may want to start the application but without any of the web framework using SpringApplicationBuilder. But sometimes you want to use custom conditions. It's pretty easy to do so, just use something like this @Component @Conditional (SchedulerCheck. class ) public class SchedulerEntryPoint implements ApplicationRunner { public static class SchedulerCheck implements Condition { @Override public boolean matches(ConditionContext conditionContext, AnnotatedTypeMetadata annotatedTypeMetadata) { return System. getProperty ( "scheduler" ) != ...
Post a Comment
Read more