Recursion recursive recursively.

Today we will discuss about recursion. Don’t you know what is the recursion? Don’t worry, now we are going to talk about recursion. Don’t you know what is the recursion? Don’t worry, now we are going to talk about recursion. Don’t you know what is the recursion?  Don’t worry, now we are going to talk about recursion. Do …. Well, as a joke it’s ok 🙂

Because Scala is a language that, despite being object-oriented, its true potential lies largely in its functional part, it is normal that recursion has a special importance. However, even more important, it is to generate the recursive calls properly to not have a stack overflow.

Stack Overflow: plus a pretty famous page, is what happens when we perform many recursive calls and, in consequence, the stack memory is overflowed.

szpjhwz

In order to generate recursive calls properly it is necessary that the function will be tail-recursive. This means that the function needn’t to stored in memory the result of the recursive call. Thus, a stack overflow is not triggered. It can also be seen as a recursive function when the function only calls itself with different arguments. Examples of functions that do not meet the tail-recursive condition are those in which operations are performed with the results of the recursive calls. For example, the factorial function encoded on this way:

def factorial(n: Int): Int =
  if (n <= 1) 1
  else n * factorial(n - 1)

because the call is multiplied by n, it will not perform a tail-recursive recursion.

And how do you know if a function is tail-recursive? Scala makes the whole thing easy. We can add the tailRecursive annotation in this function so that if it has not been written on a tail-recursive way, Scala return us a compilation error. The compiler makes the work for us 🙂

Let’s see how we can build a function which returns the element n of the Fibonacci sequence (a tipical example). First without tail-recursive:

@annotation.tailrec
def fibonacci(n : Int) : Int = n match {
  case 0 | 1 => n
  case _ => fibonacci( n-1 ) + fibonacci( n-2 )
}

This returns a compilation error like this:

“could not optimize @tailrec annotated method fibonacci: it contains a recursive call not in tail position”

However, if we think a little more we can get it a function much efficient 🙂

def fibonacci(n: Int): Int = {

  @annotation.tailrec
  def loop(i: Int, previous: Int, current: Int): Int =
    if (i == 0) previous
    else loop(i - 1, current, previous + current)

  loop(n, 0, 1)
}

In this case there will be no compilation error.

28b5865ebe59280d5c3ed18fc1147964309d9d0c81663c0c3f81d42fc5979c8f

And that’s all. And that’s all. And that’s …

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s