Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

The Tale of ‘Tail Recursion’

DZone's Guide to

The Tale of ‘Tail Recursion’

Recursive problem solving doesn't scale well. Fortunately, you can get your compiler to transform your into an iterative process to solve the problem.

· Java Zone
Free Resource

The single app analytics solutions to take your web and mobile apps to the next level.  Try today!  Brought to you in partnership with CA Technologies

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 highly expressive. For example, consider this factorial function:

imageedit_2_7440821029

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

imageedit_4_3062358181

Recursions don’t scale very well for large input sizes. And in practical way, I want to use recursions when the problem size is complex and big. So, it kind of defeats the purpose. You can't use it when you need it the most.

This is where a fairly interesting set of 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 an optimized one when we run it.

We can write such code in the following ways:

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

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

  • Another technique is to use some compiler magic if we can to write code as a recursive procedure and transform it into an iterative process under the covers. An implementation with this property is called tail-recursive.

imageedit_16_7482961416

So, now it is working and the stack didn’t blow up this time. In order to see how it works, let's analyze the stack trace of both functions:

imageedit_10_4364322468

In a normal recursive function, we are five levels deep. 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 we have only one level of stack is that the compiler was able to optimize it. Very quietly under the covers, the compiler modified this recursion into a simple iteration.

I hope this has been helpful!

CA App Experience Analytics, a whole new level of visibility. Learn more. Brought to you in partnership with CA Technologies.

Topics:
java ,scala ,tail recursion ,problem solving ,tutorial

Published at DZone with permission of Mahesh Chand Kandpal, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}