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

Recursividad recursivamente recursiva

Hoy hablaremos de la recursividad. ¿No sabés lo que es la recursividad? No te preocupes, hoy hablaremos de la recursividad. ¿No sábes lo que es la recursividad? No te preocupes, hoy hablaremos de la recursividad. ¿No sabes lo que es la recursividad? No te preocupes, hoy hablaremos de la recursividad. ¿No sa….bueno, como broma ya está bien 🙂

Debido a que Scala es un lenguaje que, a pesar de ser orientado a objetos, su verdadero potencial reside en gran parte en su parte funcional, es normal que la recursividad sea un factor importante. Sin embargo, aún más importante es generar las llamadas recursivas de forma correcta para no provocar un stack overflow.

Stack Overflow: además de una página bastante famosa, es lo que ocurre cuando realizamos tantas llamadas recursivas que la pila de memoria se llena.

szpjhwz

Para generar las llamadas recursivas de forma correcta es necesario que la función sea tail-recursive. Esto quiere decir, que la función no necesita guardarse nada en memoria a la espera del resultado de la llamada recursiva. De esta forma no se provocará un overflow de la pila. También puede verse como una función que en el caso recursivo solamente se llama a si misma con distintos argumentos. Ejemplos de funciones que no cumplen la condición tail-recursive son aquellas en las que se realizan operaciones con los resultados de las llamadas recursivas. Por ejemplo, la función factorial codificada de la siguiente manera:

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

al estar multiplicada la llamada por n, no cumplirá una recursividad tail-recursive

¿Y cómo saber si una función es tail-recursive? Scala nos lo pone fácil. Podemos añadir la anotación tailRecursive en dicha función para que en caso de que no se haya codificado de forma tail-recursive, Scala nos devuelva un error de compilación. El compilador nos hace el trabajo 🙂

Vamos a ver como lo haríamos con la función que nos devuelve el elemento n de la sucesión de Fibonacci (un clásico). En primer lugar sin tail-recursive:

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

Esto nos devuelve un error de compilación tal que así:

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

Sin embargo, si pensamos un poco más podremos conseguir la misma función mucho más eficiente 🙂

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)
}

En este caso no habrá ningún error de compilación.

28b5865ebe59280d5c3ed18fc1147964309d9d0c81663c0c3f81d42fc5979c8f

Y hasta aquí este post. Y hasta aquí este post. Y hasta aquí este …