Recursividad

Uno de los conceptos más importantes en ciencias de la computación es la recursividad, entendida esta como la propiedad de un programa para llamarse a sí mismo. En muchos ámbitos la recursividad permite crear programas computacionales que resuelven problemas de forma eficiente.

En esta publicación explicaremos en mayor detalle el concepto de recursividad y sus aplicaciones comunes en ciencias de la computación.

Dentro de las principales aplicaciones de recursividad tenemos los algoritmos de búsqueda, algoritmos de ordenamiento, programación dinámica, etc.

Funciones Recursivas

Se denomina función recursiva a una función que se llama a sí misma.

Una función recursiva bien definida tendrá dos casos principales: (1) el caso o ruta de ejecución recursiva y (2) el caso base o punto de parada que es la condición que al cumplirse hace que la función deje de llamarse a sí misma y devuelva un resultado.

Consieremos el siguiente programa:

let contador = 0;

function fnRecursiva() {
   if(contador > 5){
      return "Listo: " + contador;
   }
   contador ++;
   return fnRecursiva();
}

Se define una variable contador y una función llamada fnRecursiva(). El caso base en la linea 4 determina que si la variable contador es mayor a 5 la función sale devolviendo la cadena compuesta por la palabra «Listo: » y el valor de la variable contador.

En caso contrario (si contador no es mayor a 5) se suma 1 a dicha variable y se llama de nuevo a fnRecursiva(). Esta parte correspondería a la ruta recursiva; es decir la parte de la lógica que se llama a sí misma.

En el curso «Master the Coding Interview: Big Tech (FAANG) Interviews» en la lectura #269 titulada «Anatomy of Recursion», se mencionan tres pasos fundamentales para definir una función recursiva de forma apropiada:

1. Identificar el caso base o punto de parada (línea 4)
2. Identificar el caso recursivo (línea 7)
3. Definir una lógica de aproximación al caso base (línea 7) y que retorne un valor cuando se alcance este punto (línea 5). Se identifican al menos dos retornos de valor, uno para el caso base (línea 5) y uno para el caso recursivo. (línea 8)

Comparación entre recursividad e iteratividad

Existe una teoría que dice que «cualquier solución implementada por recusividad puede ser también implementada por iteratividad».

El siguiente programa de ejemplo muestra una implementación recursiva y otra iterativa para calcular una secuencia fibonacci.

(() => {
    function fibonacci_iterative(n) {
        let arr = [0, 1];
        for (let i = 2; i < n + 1; i++) {
            arr.push(arr[i-2]+arr[i-1]);
        }

        return arr[n];
    }

    function fibonacci_recursive(n){
        if (n<2){
            return n;
        } else {
            return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
        }
    }

    exports.Fibonacci_I = fibonacci_iterative;
    exports.Fibonacci_R = fibonacci_recursive;
})();

En nuestro paquete de npm jn-didactic realizamos algunas pruebas de escala en el script test/test-fibonacci.js donde vemos que la implementación iterativa para n=20 se ejecuta en menos de 1 segundo mientras que la recursiva se ejecuta en más de 3 segundos.

Algunas de las ventajas de la lógica recusiva es que es más legible y previene la necesidad de repetir piezas de la lógica varias veces en nuestros programas. Una de las desventajas más notorias es que se puede fácilmente agotar los recursos disponibles para la ejecución del programa.

La lógica recursiva sin embargo presenta beneficios de simplicidad para problemas complejos que tengan que ver con travesía de estructuras de datos, búsquedas de tipo BFS y DFS, y para algoritmos de ordenamiento que y búsqueda; así como para operaciones en estructuras de datos tipo árbol.

Divide y Conquista: este paradigma consiste en dividir un problema en sub-problemas más sencillos que sean idénticos en naturaleza, y que puedan ser combinados para obtener una solución final.

Recursividad de Cola (Tail Recursion)

Un fenómeno interesante y a la vez relacionado con la capacidad de optimizar la recursividad es el que se da en llamadas recursivas «pendientes» en contraste con llamadas recursivas «tail» o «de cola».

Si consideramos las siguientes dos funciones para calcular un factorial, vemos que tenemos una que es «_tail» y otra «normal».

    function factorial(n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    function factorial_tail(n, totalSoFar = 1) {
        if (n === 0) return totalSoFar;
        return factorial_tail(n - 1, totalSoFar * n);
    }

La función factorial(n) es menos eficiente que la función factorial_tail(n, totalSoFar = 1)

Esta diferencia en eficiencia ocurre por la forma en que está pensado el caso recursivo (líneas 3 y 8): mientras que en la línea 8 se hace una llamada recursiva pura con todos los parámetros resueltos y donde simplemente se busca retornar el resultado de la función que se está llamando, en la línea 3 se hace una llamada recursiva que además genera un cálculo pendiente que consiste en multiplicar el valor de x por el resultado de la llamada recursiva. El caso de la línea 3 es más dificil de resolver en tiempo de ejecución porque necesita esperar a que se resuelva la llamada recursiva para realizar un cálculo adicional ( n * resultado )

 5,111 total views,  3 views today