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 …

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