The Tale of ‘Tail Recursion’


Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).

Recursions are really cool and they are highly expressive. For example consider factorial function:

imageedit_2_7440821029

But if i increase the size of input, code will blow up.

imageedit_4_3062358181

Recursions don’t scale very well for large input sizes. And in practical way, when i use the recursion when problem size is complex and big. So, its kind of defeat when you need it most you can’t use it.

This is where fairly set of interesting techniques come in.

Distinction between a procedure and process.

Procedure: The code we write.

Process: The code that runs.

So essentially, the idea is to write a piece of code that gets transformed into optimized one when we run it.

We can write code in following ways:

we can write code in iterative procedure and run it as iterative process. But it is not expressive.

And we can write code in recursive procedure and run it as recursive process. Unfortunately, it does not scale. When Input size gets big, it fails.

Another technique, use some compiler magic if we can, To write code as recursive procedure and gets transformed into iterative process under the covers.

An implementation with this property is called tail-recursive.

imageedit_16_7482961416

So, now it is working and stack didn’t blow up this time.

In order to see how it is working, lets analyze the stack trace of both functions:

imageedit_10_4364322468

In normal recursive function, we are five level deep in stack. Now let’s see the stack trace of tail recursive code.

imageedit_12_5615457333

Notice the difference in output, the point here is that there is only one level of stack. Structurally, we didn’t reduce number of recursive calls. We are still going through five recursions. The reason is why we have only one level of stack, Compiler was able to optimize it. Very quietly under the covers, compiler modified this recursion into simple iteration.

Hope that this blog is helpful for you.

Reference:

  1. Structure and interpretation of computer programs by Gerald Jay Sussman and Hal Abelson

About Mahesh Chand Kandpal

Explorer + Technology Enthusiast + Foodie + Movie Buff
This entry was posted in Scala and tagged , , . Bookmark the permalink.

4 Responses to The Tale of ‘Tail Recursion’

  1. Ashish says:

    Very nice article brother. I have a question though — Is tail recursion a computer science phenomenon ( a generic solution available for all compilers / programming languages) or it’s the enhancement provided by only some specific compilers (e.g. Scala compiler) ?

    • Compiler and libraries may opt to make use of the general concept/idea. Not all compiler, languages, language libraries do. For example, Haskell does, Java does not, Scala does, Groovy compiler does not, but Groovy GDK library does, etc.

  2. Pingback: Jump Higher With Trampoline | Knoldus

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s