Recursión (ciencias de computación)

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:

${\displaystyle \operatorname {fact} (n)=\left\{{\begin{array}{lccl}si&n=0&\longrightarrow &1\\si&n>0&\longrightarrow &n\cdot \operatorname {fact} (n-1)\\\end{array}}\right.}$

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.[6]

Relación recurrente de un factorial:

${\displaystyle b_{n}=nb_{n-1}}$

${\displaystyle b_{0}=1}$

b4           = 4 * b3

             = 4 * 3 * b2
             = 4 * 3 * 2 * b1
             = 4 * 3 * 2 * 1 * b0
             = 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:

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.

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:

${\displaystyle \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.}$

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

  b4            = b3 + b2
                = b2 + b1 + b1 + b0
                = b1 + b0 + 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.[7]

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:

${\displaystyle \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.}$

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 ${\displaystyle x\%y}$ expresa el resto de la división entera ${\displaystyle x/y}$:

${\displaystyle \gcd(x,y)=\gcd(y,x\%y)}$

${\displaystyle \gcd(x,0)=x}$

gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9

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. ",[8] al español "número de pasos crece a medida que lo hace el logaritmo de los números involucrados."

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.

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.[9][10] 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:

${\displaystyle \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:

${\displaystyle h_{n}=2h_{n-1}+1}$

${\displaystyle h_{1}=1}$

hanoi(4)     = 2*hanoi(3) + 1
             = 2*(2*hanoi(2) + 1) + 1
             = 2*(2*(2*hanoi(1) + 1) + 1) + 1
             = 2*(2*(2*1 + 1) + 1) + 1
             = 2*(2*(3) + 1) + 1
             = 2*(7) + 1
             = 15

Ejemplos de implementación:

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.[11]

h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1

Por lo general:
hn = 2n - 1, for all n >= 1

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

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."[12]

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.[13]

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

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.

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.