Algoritmos Recursivos

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Las claves para construir un subprograma recurrente son:

Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.

Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

Un método frecuente para simplificar es dividir un problema en problemas derivados de menor tamaño del mismo tipo. Esto se conoce como dialecting. Como técnica de programación se denomina divide y vencerás y es pieza fundamental para el diseño de muchos algoritmos de importancia, así como parte esencial de la programación dinámica.

Virtualmente todos los lenguajes de programación modernos permiten la especificación directa de funciones y subrutinas recursivas. Cuando se llama una función de este tipo, el ordenador, para la mayoría de los lenguajes en casi todas las arquitecturas basadas en una pila (stack) o en la implementación del lenguaje, lleva la cuenta de las distintas instancias de la función, en numerosas arquitecturas mediante el uso de un call stack, aunque no de forma exclusiva. A la inversa, toda función recursiva puede transformarse en una función iterativa usando un stack.

La mayoría (aunque no todas) de las funciones y subrutinas que pueden ser evaluadas por un ordenador, pueden expresarse en términos de una función recursiva (sin tener que utilizar una iteración pura); a la inversa, cualquier función recursiva puede expresarse en términos de una iteración pura, dado que la recursión es, de por sí, también iterativa. Para evaluar una función por medio de la recursión, tiene que definirse como una función de sí misma (ej. el factor n! = n * (n - 1)! , donde 0! se define como 1). Resulta evidente que no todas las evaluaciones de funciones se prestan a un acercamiento recursivo. Por lo general, todas las funciones finitas pueden describirse directamente de forma recursiva; las funciones infinitas (ej. las series de e = 1/1! + 2/2! + 3/3!...) necesitan un criterio extra para detenerse, ej. el número de iteraciones, o el número de dígitos significativos, en caso contrario una iteración recursiva resultaría en un bucle infinito.

A modo de ilustración: Si se encuentra una palabra desconocida en un libro, el lector puede anotar la página actual en un papel y ponerlo en una pila (hasta entonces vacía). El lector consulta la palabra en otro artículo y, de nuevo, descubre otra palabra desconocida, la anota y la pone en la pila, y así sucesivamente. Llega un momento que el lector lee un artículo que donde todas las palabras son conocidas. El lector retorna entonces a la última página y continua la lectura desde ahí, y así hasta que se retira la última nota de la pila retornando entonces al libro original. Este modus operandi es recursivo.

Algunos lenguajes diseñados para programación lógica y programación funcional ofrecen la recursión como el único medio de repetición directa disponible para el programador. Estos lenguajes suelen conseguir que la recursión de cola sea tan eficiente como la iteración, permitiendo a los programadores expresar otras estructuras repetitivas (tales como map y for de scheme) en términos de recursión.

La recursión está profundamente anclada en la teoría de computación, con la equivalencia teórica de función microrecursiva y máquinas de Turing en la cimentación de ideas sobre la universalidad del ordenador moderno.

Programación recursiva

Crear una subrutina recursiva requiere principalmente la definición de un "caso base", y entonces definir reglas para subdividir casos más complejos en el caso base. Para una subrutina recursiva es esencial que con cada llamada recursiva, el problema se reduzca de forma que al final llegue al caso base.

Algunos expertos clasifican la recursión como "generativa" o bien "estructural". La distinción se hace según de donde provengan los datos con los que trabaja la subrutina. Si los datos proceden de una estructura de datos similar a una lista, entonces la subrutina es "estructuralmente recursiva"; en caso contrario, es "generativamente recursiva".

Muchos algoritmos populares generan una nueva cantidad de datos a partir de los datos aportados y recurren a partir de ahí. HTDP (How To Design Programs), al español, "Cómo diseñar programas", se refiere a esta variante como recursión generativa. Ejemplos de recursión generativa incluyen: máximo común divisor, quicksort, búsqueda binaria, mergesort, Método de Newton, fractals e integración adaptiva.

Ejemplos de subrutinas definidas recursivamente (recursión generativa)

Factorial

Un ejemplo clásico de una subrutina recursiva es la función usada para calcular el factorial de un entero.

Definición de la función:

Pseudocódigo (recursivo):
función factorial: input: entero n de forma que n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n es 0, return 1 2. else, return [ n × factorial(n-1) ] end factorial

Una relación recurrente es una ecuación que relaciona términos posteriores en la secuencia con términos previos.

Relación recurrente de un factorial:

b_{n}=nb_{n-1}

b_{0}=1

Computando la relación recurrente para n = 4:
b₄ = 4 * b₃ = 4 * 3 * b₂ = 4 * 3 * 2 * b₁ = 4 * 3 * 2 * 1 * b₀ = 4 * 3 * 2 * 1 * 1 = 4 * 3 * 2 * 1 = 4 * 3 * 2 = 4 * 6 = 24

Esta función factorial también puede describirse sin usar recursión haciendo uso de típicas estructuras de bucle que se encuentran en lenguajes de programación imperativos:

Pseudocódigo (iterativo):
función factorial es: input: entero n de forma que n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. crear una variable nueva llamada running_total con un valor = 1 2. begin loop 1. si n es = 0, salir del loop 2. cambiar running_total a (running_total × n) 3. decrementar n 4. repetir el loop 3. return running_total end factorial

Pseudocódigo (iterativo):

función factorial es:

input: entero n de forma que n >= 0

output: [n × (n-1) × (n-2) × … × 1]


    1. crear una variable nueva llamada running_total con un valor = 1


    2. begin loop
          1. si n es = 0, salir del loop
          2. cambiar running_total a (running_total × n)
          3. decrementar n
          4. repetir el loop


    3. return running_total


end factorial

El lenguaje de programación scheme es, sin embargo, un lenguaje de programación funcional y no define estructuras de loops de cualquier tipo. Se basa únicamente en la recursión para ejecutar todo tipo de loops. Dado que scheme es recursivo de cola, se puede definir una subrutina recursiva que implementa la subrutina factorial como un proceso iterativo, es decir, usa espacio constante pero tiempo lineal.

Fibonacci

Otra popular secuencia recursiva es el Número de Fibonacci. Los primeros elementos de la secuencia son: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Definición de la función:

\operatorname {fib} (n)=\left\{{\begin{array}{lccl}si&n=0&\longrightarrow &0\\si&n=1&\longrightarrow &1\\si&n>2&\longrightarrow &\operatorname {fib} (n-2)+\operatorname {fib} (n-1)\\\end{array}}\right.

Pseudocódigo
function fib is: input: entero n de forma que n >= 0 1. si n es = 0, return 0 2. si n es = 1, return 1 3. else, return [ fib(n-1) + fib(n-2) ] end fib

Relación recurrente para Fibonacci:

b_n = b_n-1 + b_n-2

b₁ = 1, b₀ = 0

Computando la relación recurrente para n = 4:
b₄ = b₃ + b₂ = b₂ + b₁ + b₁ + b₀ = b₁ + b₀ + 1 + 1 + 0 = 1 + 0 + 1 + 1 + 0 = 3

Este algoritmo de Fibonacci es especialmente malo pues cada vez que se ejecuta la función, realizará dos llamadas a la función a sí misma, cada una de las cuales hará a la vez dos llamadas más y así sucesivamente hasta que terminen en 0 o en 1. El ejemplo se denomina "recursión de árbol", y sus requisitos de tiempo crecen de forma exponencial y los de espacio de forma lineal.

Máximo común divisor

Otro famosa función recursiva es el algoritmo de Euclides, usado para computar el máximo común divisor de dos enteros.

Definición de la función:

\operatorname {mcd} (x,y)=\left\{{\begin{array}{llcl}si&y=0&\longrightarrow &x\\si&y>0\;\land \;x\geq y&\longrightarrow &\operatorname {mcd} (y,mod(x,y))\end{array}}\right.

Pseudocódigo (recursivo):
function gcd is: input: entero x, entero y de forma que x >= y y y > 0 1. if y is 0, return x 2. else, return [ gcd( y, (remainder of x/y) ) ] end gcd

Relación recursiva del máximo común denominador, donde $x\%y$ expresa el resto de la división entera $x/y$ :

\gcd(x,y)=\gcd(y,x\%y)

\gcd(x,0)=x

Computando la relación recurrente para x = 27 e y = 9:
gcd(27, 9) = gcd(9, 27 % 9) = gcd(9, 0) = 9
Computando la relación recurrente para x = 259 e y = 111:
gcd(259, 111) = gcd(111, 259 % 111) = gcd(111, 37) = gcd(37, 0) = 37

Nótese que el algoritmo "recursivo" mostrado arriba es, de hecho, únicamente de cola recursiva, lo que significa que es equivalente a un algoritmo iterativo. En el ejemplo siguiente se muestra el mismo algoritmo usando explícitamente iteración. No acumula una cadena de operaciones deferred, sino que su estado es, más bien, mantenido completamente en las variables x e y. Su "number of steps grows the as the logarithm of the numbers involved. ", al español "número de pasos crece a medida que lo hace el logaritmo de los números involucrados."

Pseudocódigo:
función gcd es: input: entero x, entero y de forma que x >= y e y > 0 1. crear una nueva variable llamada remainder 2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop 3. return x end gcd

Pseudocódigo:

función gcd es:

input: entero x, entero y de forma que x >= y e y > 0


    1. crear una nueva variable llamada remainder


    2. begin loop
          1. if y is zero, exit loop
          2. set remainder to the remainder of x/y
          3. set x to y
          4. set y to remainder
          5. repeat loop


    3. return x


end gcd

El algoritmo iterativo requiere una variable temporal, e incluso supuesto el conocimiento del Algoritmo de Euclides es más difícil de entender el proceso a simple vista, aunque los dos algoritmos son muy similares en sus pasos.

Torres de Hanói

Para una detallada discusión de la descripción de este problema, de su historia y de su solución, consúltese el artículo principal. El problema, puesto de forma simple, es el siguiente: Dadas 3 pilas, una con un conjunto de N discos de tamaño creciente, determina el mínimo (óptimo) número de pasos que lleva mover todos los discos desde su posición inicial a otra pila sin colocar un disco de mayor tamaño sobre uno de menor tamaño.

Definición de la función:

\operatorname {hanoi} (n)=\left\{{\begin{array}{lccl}si&n=1&\longrightarrow &1\\si&n>1&\longrightarrow &2\cdot \operatorname {hanoi} (n-1)+1\end{array}}\right.

Relación de recurrencia para hanoi:

h_{n}=2h_{n-1}+1

h_{1}=1

Computación de la relación de recurrencia para n = 4:
hanoi(4) = 2hanoi(3) + 1 = 2(2hanoi(2) + 1) + 1 = 2(2(2hanoi(1) + 1) + 1) + 1 = 2(2(21 + 1) + 1) + 1 = 2(2(3) + 1) + 1 = 2(7) + 1 = 15

Ejemplos de implementación:

Pseudocódigo (recursivo):
function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi

Aunque no todas las funciones recursivas tienen una solución explícita, la secuencia de la Torre de Hanói puede reducirse a una fórmula explícita.

Una fórmula explícita de las Torres de Hanói:
h₁ = 1 = 2¹ - 1 h₂ = 3 = 2² - 1 h₃ = 7 = 2³ - 1 h₄ = 15 = 2⁴ - 1 h₅ = 31 = 2⁵ - 1 h₆ = 63 = 2⁶ - 1 h₇ = 127 = 2⁷ - 1 Por lo general: h_n = 2ⁿ - 1, for all n >= 1

Búsqueda binaria

El algoritmo de búsqueda binaria es un método de búsqueda de un dato en un vector de datos ordenado dividiendo el vector en dos tras cada pasada. El truco es escoger un punto cerca del centro del vector, comparar en ese punto el dato con el dato buscado para responder entonces a una de las siguientes 3 condiciones: se encuentra el dato buscado, el dato en el punto medio es mayor que el valor buscado o el dato en el punto medio es menor que el valor buscado.

Se usa recursión en este algoritmo porque tras cada pasada se crea un nuevo vector dividiendo en original en dos. La subrutina de búsqueda binaria se llama entonces de forma recursiva, cada vez con un vector de menor tamaño. El tamaño del vector se ajusta normalmente cambiando el índice inicial y final. El algoritmo muestra un orden logaritmo de crecimiento porque divide esencialmente el dominio del problema en dos tras cada pasada.

Ejemplo de implementación de la búsqueda binaria:

 /*
  Call binary_search with proper initial conditions.
  
  Entrada: 
    Los datos se presentan en forma de vector de [[número entero|números enteros]] ordenado de forma ascendente,
    ''toFind'' es el número entero a buscar,
    ''count'' es el número total de elementos del vector
           
  Salida:
    resultado de la búsqueda binaria
   
 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (índice inicial)
    //  End = count - 1 (índice superior)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Algoritmo de la búsqueda binaria.
   
   Entrada: 
        Los datos se presentan en forma de vector de [[número entero|números enteros]] ordenado de forma ascendente,
        ''toFind'' es el número entero a buscar,
        ''start'' es el índice mínimo del vector,
        ''end'' es el índice máximo del vector
   Salida: 
        posición del número entero ''toFind'' dentro del vector de datos, 
        -1 en caso de búsqueda fallida
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Averigua el punto medio.
    int mid = start + (end - start)/2;   //División de enteros
    
    //Condición para detenerse.
    if (start > end)
       return -1;
    else if (data[mid] == toFind)        //Encontrado?
       return mid;
    else if (data[mid] > toFind)         //El dato es mayor que ''toFind'', se busca en la mitad inferior
       return binary_search(data, toFind, start, mid-1);
    else                                 //El dato es menor que ''toFind'', se busca en la mitad superior
       return binary_search(data, toFind, mid+1, end);
 }

Estructuras de datos recursivo (recursión estructural)

Una aplicación de importancia de la recursión en ciencias de la computación es la definición de estructuras de datos dinámicos tales como listas y árboles. Las estructuras de datos recursivos pueden crecer de forma dinámica hasta un tamaño teórico infinito en respuesta a requisitos del tiempo de ejecución; por su parte, los requisitos del tamaño de un vector estático deben declararse en el tiempo de complicación.

"Los algoritmos recursivos son especialmente apropiados cuando el problema que resolver o los datos que manejar son definidos en términos recursivos."

Los ejemplos en esta sección ilustran lo que se conoce como "recursión estructural". Este término se refiere al hecho de que las subrutinas recursivas se aplican a datos que se definen de forma recursiva.

En la medida en que un programador deriva una plantilla de una definición de datos, las funciones emplean recursión estructural. Es decir, las recursiones en el cuerpo de una función consumen una determinada cantidad de un compuesto dado de forma inmediata.

Listas enlazadas

A continuación se describe una definición simple del nodo de una lista enlazada. Nótese como se define el nodo por sí solo. El siguiente elemento del nodo del struct es un puntero a un nodo de struct.

struct node
{
  int n;              // algún tipo de datos
  struct node *next;  // puntero a otro nodo de ''struct''
};

// LIST no es otra cosa que un nodo de ''struct'' *.
typedef struct node *LIST;

Las subrutinas que operan en la estructura de datos de LIST pueden implementarse de forma natural como una subrutina recursiva porque la estructura de datos sobre la que opera (LIST) es definida de forma recursiva. La subrutina printList definida a continuación recorre la lista hacia abajo hasta que ésta se vacía (NULL), para cada nodo imprime el dato (un número entero). En la implementación en C, la lista permanece inalterada por la subrutina printList.

void printList(LIST lst)
{
    if (!isEmpty(lst))         // caso básico
    {
       printf("%d ", lst->n);  // imprime el entero seguido por un espacio
       printList(lst->next);   // llamada recursiva
    }
}

Árboles binarios

Más abajo se muestra una definición simple de un nodo de árbol binario. Al igual que el nodo de listas enlazadas, se define a sí misma (de forma recursiva). Hay dos punteros que se refieren a sí mismos – left (apuntando a l aparte izquierda del subárbol) y right (a la parte derecha del subárbol).

struct node
{
  int n;               // algún tipo de datos
  struct node *left;   // puntero al subárbol izquierdo
  struct node *right;  // puntero al subárbol derecho
};

// TREE no es otra cosa que un nodo '' struct ''
typedef struct node *TREE;

Las operaciones en el árbol pueden implementarse usando recursión. Nótese que, debido al hecho de que hay dos punteros que se referencian a sí mismos (izquierda y derecha), esas operaciones del árbol van a necesitar dos llamadas recursivas. Para un ejemplo similar, véase la función de Fibonacci y la explicación siguiente.

void printTree(TREE t) {
        if (!isEmpty(t)) {            // caso básico                          
                printTree(t->left);   // ir a la izquierda
                printf("%d ", t->n);  // imprimir el entero seguido de un espacio
                printTree(t->right);  // ir a la derecha
        }
}

El ejemplo descrito ilustra un árbol binario de orden transversal. Un árbol de búsqueda binaria es un caso especial de árbol binario en el cual los datos de cada árbol están en orden.

Recursión frente a iteración

En el ejemplo "factorial" la implementación iterativa es probablemente más rápida en la práctica que la recursiva. Esto es casi definido por la implementación del algoritmo euclidiano. Este resultado es lógico, pues las funciones iterativas no tienen que pagar el exceso de llamadas de funciones como en el caso de las funciones recursivas, y ese exceso es relativamente alto en muchos lenguajes de programación (nótese que mediante el uso de una lookup table es una implementación aún más rápida de la función factorial).

Hay otros tipos de problemas cuyas soluciones son inherentemente recursivas, porque estar al tanto del estado anterior. Un ejemplo es el árbol transversal; otros incluyen la función de Ackermann y el algoritmo divide y vencerás tales como Quicksort. Todos estos algoritmos pueden implementarse iterativamente con la ayuda de una pila, pero la necesidad del mismo, puede que anule las ventajas de la solución iterativa.

Otra posible razón para la utilización de un algoritmo iterativo en lugar de uno recursivo es el hecho de que en los lenguajes de programación modernos, el espacio de stack disponible para un hilo es, a menudo, mucho menos que el espacio disponible en el montículo, y los algoritmos recursivos suelen requerir más espacio de stack que los algoritmos iterativos. Véase, por otro lado, la sección siguiente que trata el caso especial de la recursión de cola.

Estructura Discreta