Design, Lógica

Tail-recursive algorithms

What is a tail recursive algorithm?

 

  If you’re a programmer for some time now, you probably know what a recursive function/method is. I mean, if you don’t, you probably shouldn’t be here in the first
place. This is NOT the place to be learning this kind of stuff… Just kidding. I shouldn’t be explaining this here but I will anyway. Firstly because I am one of those good guys, you know? Also because my mom taught me to be kind to people. But mainly because it’s straightforward: A recursive function is one that calls itself. Pretty much like a dog trying to bite his own tail. An algorithm to implement the Fibonacci sequence could be made recursive, for instance this one in Scala (and I’m gonna use this language in this post as I’m getting familiar with the language):


def fibonacci(x: Int): Int =
 if(x == 0 || x == 1) 1
 else fibonacci(x-1) + fibonacci(x-2)

  Alright! It’s a piece of cake in theory really. In practice? Well, not exactly. It can be very very frustrating, especially if you have a bigger function and you need
to debug it (Debug Hell). Cool. No, wait! But what about this tail-recursive thing? In traditional recursion, you perform your recursive calls first and only then you
use the returned values to calculate the result. For example, take the traditional implementation of the factorial function.


def fat(x: Int): Int =
  if(x <= 1) 1
  else x*fat(x-1)

It would be calculated like this:


fat(4) =
 4*(fat(3)) =
 4*(3*fat(2)) =
 4*(3*(2*fat(1))) =
 4*3*2*1 = 24

In tail-recursive style though, you perform the calculations first and then the recursive call is executed, passing the current result to the next recursive step.
Still using the factorial:


def loop(y: Int, x: Int):Int =
 {
    if(x <= 1) y;
    else {
      val sum: Int = y*x;
      loop(sum, x-1);
    }

}

def fat(n: Int) = loop(1,n)

In this case, we have an accumulator that already has the partial result and only passes it to the next recursion, if there is one:


fat(4) =
 loop(1,4) =
 loop(4,3) =
 loop(12,2) =
 loop(24, 1) =
 24



“Tail-recursive or not tail-recursive: that is the question!”


  Notice in this last example there is no calculation after the recursion. The recursive call is the last action in the function. Nothing else. That pretty much differentiates a tail-recursion algorithm. In a general way, if the last action of a function is to call a function (itself or another one), only one stack frame would be necessary for both. This type of call is known as a “tail call”. But what is a stack frame after all? And what difference does it make to reuse a stack frame?



“A Stack frame, a Stack frame. My kingdom for a Stack frame!”


To run your code, the Virtual Machine uses a special architecture to manage all the variables and methods in memory. For example, in the JVM memory is divided in 4 types: Heap (where instance variables, references and objects go), Stack(containing methods and the order of calls), code (contains the bytecode) and static (keeps static data and methods).

So stacks. Imagine a big stack in memory to keep the calls to your methods. Say you have a method prepare() that calls doSomething() and this last one calls doSomethingElse(). In the stack, they would be in that same order bottom-up (see picture 1). Of course, these methods have data like local variables and stuff, so where do they keep this data? On the method’s frame. The elements in the stack are called “frames”. These frames are simply blocks in memory that stores a method call and its data just like explained before.

Picture 1

Picture 1: In the picture you see the stack executing a method call. Notice that every new call is put on top of the last one, i.e the lower one is the first in Stack (top).



Back on the tail-recursive algorithms. Think about it: if one can reuse the stack frame for different calls, the execution uses constant stack space, which means the function is executed as a simple loop. Yes, there is an equivalence between a tail-recursive function and a loop. Which means you can convert a while loop, for example, into a tail-recursive function and vice-versa! It can be a big deal for the VM executing your code to reuse the current stack frame time and time again especially in deep recursions. You avoid the trap of falling into a stackoverflow error, which is basically a stack running out of stack frames. And clearly this allows for some optimization. However, if you find yourself in a situation where you have a clean non tail-recursive function (like fibonacci or factorial above) but there’s no risk to get a StackOverflow error because you’re not running deep recursion chains, so don’t lose your sleep on it. Clarity and good design are often more important aspects of an application than computational efficiency. Though, learning this feature of functional programming can help you if you need a different recursive strategy. Who knows?

Padrão

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s