Recursión (informática) - Recursion (computer science)

Árbol creado con el lenguaje de programación Logo y que se basa en gran medida en la recursividad. Cada rama puede verse como una versión más pequeña de un árbol.

En ciencias de la computación , la recursividad es un método para resolver un problema donde la solución depende de soluciones a instancias más pequeñas del mismo problema. Estos problemas generalmente se pueden resolver mediante iteración , pero esto necesita identificar e indexar las instancias más pequeñas en el momento de la programación. La recursividad resuelve estos problemas recurrentes mediante el uso de funciones que se llaman a sí mismas desde su propio código. El enfoque se puede aplicar a muchos tipos de problemas y la recursividad es una de las ideas centrales de la informática.

El poder de la recursividad reside evidentemente en la posibilidad de definir un conjunto infinito de objetos mediante un enunciado finito. De la misma manera, un programa recursivo finito puede describir un número infinito de cálculos, incluso si este programa no contiene repeticiones explícitas.

-  Niklaus Wirth , Algoritmos + Estructuras de datos = Programas , 1976

La mayoría de los lenguajes de programación de computadoras admiten la recursividad al permitir que una función se llame a sí misma desde su propio código. Algunos lenguajes de programación funcionales (por ejemplo, Clojure ) no definen ninguna construcción de bucle, sino que se basan únicamente en la recursividad para llamar al código repetidamente. Está demostrado en la teoría de la computabilidad que estos lenguajes sólo recursivos son Turing completo ; esto significa que son tan poderosos (se pueden usar para resolver los mismos problemas) como los lenguajes imperativos basados ​​en estructuras de control como whiley for.

Llamar repetidamente a una función desde dentro de sí misma puede hacer que la pila de llamadas tenga un tamaño igual a la suma de los tamaños de entrada de todas las llamadas involucradas. De ello se deduce que, para problemas que pueden resolverse fácilmente mediante iteración, la recursividad es generalmente menos eficiente y, para problemas grandes, es fundamental utilizar técnicas de optimización como la optimización de llamadas de cola .

Funciones y algoritmos recursivos

Una táctica común de programación de computadoras es dividir un problema en subproblemas del mismo tipo que el original, resolver esos subproblemas y combinar los resultados. Esto a menudo se conoce como el método de divide y vencerás ; cuando se combina con una tabla de búsqueda que almacena los resultados de subproblemas previamente resueltos (para evitar resolverlos repetidamente e incurrir en tiempo de cálculo adicional), puede denominarse programación dinámica o memorización .

Caso base

Una definición de función recursiva tiene uno o más casos base , es decir, entradas para las que la función produce un resultado trivialmente (sin recurrir), y uno o más casos recursivos , es decir, entradas para las que el programa se repite (se llama a sí mismo) . Por ejemplo, la función factorial se puede definir de forma recursiva mediante las ecuaciones 0! = 1 y, para todo n > 0 , n ! = n ( n - 1)! . Ninguna ecuación por sí sola constituye una definición completa; el primero es el caso base y el segundo es el caso recursivo. Debido a que el caso base rompe la cadena de recursividad, a veces también se le llama "caso de terminación".

El trabajo de los casos recursivos puede verse como dividir las entradas complejas en otras más simples. En una función recursiva correctamente diseñada, con cada llamada recursiva, el problema de entrada debe simplificarse de tal manera que eventualmente se llegue al caso base. (Las funciones que no están destinadas a terminar en circunstancias normales, por ejemplo, algunos procesos del sistema y del servidor, son una excepción a esto.) No escribir un caso base o probarlo incorrectamente puede causar un bucle infinito .

Para algunas funciones (como una que calcula la serie para e = 1/0! + 1/1! + 1/2! + 1/3! + ... ) no hay un caso base obvio implícito en los datos de entrada ; para estos se puede agregar un parámetro (como el número de términos que se agregarán, en nuestro ejemplo de serie) para proporcionar un "criterio de detención" que establece el caso base. Este ejemplo es tratado de forma más natural por correcursión , donde los términos sucesivos en la salida son las sumas parciales; esto puede ser convertido a una recursión mediante el parámetro de indexación decir "calcular el n º plazo ( n º suma parcial)".

Tipos de datos recursivos

Muchos programas de computadora deben procesar o generar una cantidad de datos arbitrariamente grande . La recursividad es una técnica para representar datos cuyo tamaño exacto es desconocido para el programador : el programador puede especificar estos datos con una definición autorreferencial . Hay dos tipos de definiciones autorreferenciales: definiciones inductivas y coinductivas .

Datos definidos inductivamente

Una definición de datos recursivos definida inductivamente es aquella que especifica cómo construir instancias de los datos. Por ejemplo, las listas enlazadas se pueden definir inductivamente (aquí, usando la sintaxis de Haskell ):

data ListOfStrings = EmptyList | Cons String ListOfStrings

El código anterior especifica que una lista de cadenas está vacía o una estructura que contiene una cadena y una lista de cadenas. La autorreferencia en la definición permite la construcción de listas de cualquier número (finito) de cadenas.

Otro ejemplo de definición inductiva son los números naturales (o enteros positivos ):

A natural number is either 1 or n+1, where n is a natural number.

De manera similar, las definiciones recursivas se utilizan a menudo para modelar la estructura de expresiones y declaraciones en lenguajes de programación. Los diseñadores de lenguajes a menudo expresan gramáticas en una sintaxis como la forma Backus-Naur ; aquí hay una gramática de este tipo, para un lenguaje simple de expresiones aritméticas con multiplicación y suma:

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Esto dice que una expresión es un número, un producto de dos expresiones o una suma de dos expresiones. Al referirse recursivamente a expresiones en la segunda y tercera líneas, la gramática permite expresiones aritméticas arbitrariamente complicadas como (5 * ((3 * 6) + 8)), con más de un producto o operación de suma en una sola expresión.

Datos y corecursion definidos de forma coinductiva

Una definición de datos coinductivos es aquella que especifica las operaciones que se pueden realizar en un dato; Normalmente, las definiciones coinductivas autorreferenciales se utilizan para estructuras de datos de tamaño infinito.

Una definición coinductiva de flujos infinitos de cadenas, dada informalmente, podría verse así:

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

Esto es muy similar a una definición inductiva de listas de cadenas; la diferencia es que esta definición especifica cómo acceder a los contenidos de la estructura de datos, es decir, a través de las funciones de accesohead y tailcuáles pueden ser esos contenidos, mientras que la definición inductiva especifica cómo crear la estructura y de qué se puede crear.

Corecursion está relacionado con la coinducción y se puede usar para calcular instancias particulares de (posiblemente) objetos infinitos. Como técnica de programación, se usa con mayor frecuencia en el contexto de lenguajes de programación perezosos y puede ser preferible a la recursividad cuando se desconoce el tamaño o la precisión deseados de la salida de un programa. En tales casos, el programa requiere tanto una definición para un resultado infinitamente grande (o infinitamente preciso) como un mecanismo para tomar una porción finita de ese resultado. El problema de calcular los primeros n números primos es uno que se puede resolver con un programa corecursivo (por ejemplo, aquí ).

Tipos de recursividad

Recursión única y recursión múltiple

La recursividad que contiene solo una autorreferencia única se conoce como recursividad única , mientras que la recursividad que contiene múltiples autorreferencias se conoce comorecursividad múltiple . Los ejemplos estándar de recursividad única incluyen recorrido de lista, como en una búsqueda lineal, o calcular la función factorial, mientras que los ejemplos estándar de recursión múltiple incluyenrecorrido de árbol, como en una búsqueda en profundidad.

La recursividad única es a menudo mucho más eficiente que la recursividad múltiple y, en general, se puede reemplazar por un cálculo iterativo, que se ejecuta en tiempo lineal y requiere un espacio constante. La recursividad múltiple, por el contrario, puede requerir tiempo y espacio exponenciales, y es más fundamentalmente recursiva, no pudiendo ser reemplazada por iteración sin una pila explícita.

La recursividad múltiple a veces se puede convertir en recursividad única (y, si se desea, de allí en iteración). Por ejemplo, mientras que calcular la secuencia de Fibonacci ingenuamente es una iteración múltiple, ya que cada valor requiere dos valores previos, se puede calcular mediante una recursividad simple pasando dos valores sucesivos como parámetros. Esto se enmarca más naturalmente como corecursion, construyéndose a partir de los valores iniciales, rastreando en cada paso dos valores sucesivos - ver corecursion: ejemplos . Un ejemplo más sofisticado es el uso de un árbol binario enhebrado , que permite un recorrido de árbol iterativo, en lugar de una recursividad múltiple.

Recursividad indirecta

La mayoría de los ejemplos básicos de recursividad, y la mayoría de los ejemplos presentados aquí, demuestran recursividad directa , en la que una función se llama a sí misma. La recursividad indirecta ocurre cuando una función no es llamada por sí misma sino por otra función a la que llamó (ya sea directa o indirectamente). Por ejemplo, si f llama a f, eso es recursividad directa, pero si f llama a g que llama a f, entonces es recursividad indirecta de f. Son posibles cadenas de tres o más funciones; por ejemplo, la función 1 llama a la función 2, la función 2 llama a la función 3 y la función 3 vuelve a llamar a la función 1.

La recursividad indirecta también se llama recursividad mutua , que es un término más simétrico, aunque esto es simplemente una diferencia de énfasis, no una noción diferente. Es decir, si f llama a gy luego g llama a f, que a su vez vuelve a llamar a g , desde el punto de vista de f solo, f está recidivando indirectamente, mientras que desde el punto de vista de g solo, está recidivando indirectamente, mientras que desde el punto de vista de ambos, f y g son recursivamente mutuamente el uno del otro. De manera similar, un conjunto de tres o más funciones que se llaman entre sí puede denominarse un conjunto de funciones recursivas entre sí.

Recursividad anónima

La recursividad generalmente se realiza llamando explícitamente a una función por su nombre. Sin embargo, la recursividad también se puede realizar llamando implícitamente a una función basada en el contexto actual, que es particularmente útil para funciones anónimas y se conoce como recursión anónima .

Recursividad estructural versus generativa

Algunos autores clasifican la recursividad como "estructural" o "generativa". La distinción está relacionada con el lugar donde un procedimiento recursivo obtiene los datos con los que trabaja y cómo procesa esos datos:

[Las funciones que consumen datos estructurados] normalmente descomponen sus argumentos en sus componentes estructurales inmediatos y luego procesan esos componentes. Si uno de los componentes inmediatos pertenece a la misma clase de datos que la entrada, la función es recursiva. Por esa razón, nos referimos a estas funciones como FUNCIONES (ESTRUCTURALMENTE) RECURSIVAS.

-  Felleisen, Findler, Flatt y Krishnaurthi, Cómo diseñar programas , 2001

Por tanto, la característica definitoria de una función estructuralmente recursiva es que el argumento de cada llamada recursiva es el contenido de un campo de la entrada original. La recursividad estructural incluye casi todos los recorridos de árboles, incluido el procesamiento XML, la creación y búsqueda de árboles binarios, etc. Al considerar la estructura algebraica de los números naturales (es decir, un número natural es cero o el sucesor de un número natural), funciones como como factorial también puede considerarse como recursividad estructural.

La recursividad generativa es la alternativa:

Muchos algoritmos recursivos conocidos generan una pieza de datos completamente nueva a partir de los datos dados y se repiten en ella. HtDP ( Cómo diseñar programas ) se refiere a este tipo como recursividad generativa. Los ejemplos de recursividad generativa incluyen: gcd , clasificación rápida , búsqueda binaria , clasificación por fusión , método de Newton , fractales e integración adaptativa .

-  Matthias Felleisen, Programación funcional avanzada , 2002

Esta distinción es importante para probar la terminación de una función.

  • Todas las funciones estructuralmente recursivas en estructuras de datos finitas ( definidas inductivamente ) se pueden mostrar fácilmente para terminar, mediante inducción estructural : intuitivamente, cada llamada recursiva recibe una pieza más pequeña de datos de entrada, hasta que se alcanza un caso base.
  • Las funciones generativamente recursivas, por el contrario, no necesariamente alimentan entradas más pequeñas a sus llamadas recursivas, por lo que la prueba de su terminación no es necesariamente tan simple, y evitar bucles infinitos requiere mayor cuidado. Estas funciones generativamente recursivas a menudo se pueden interpretar como funciones corecursivas (cada paso genera los nuevos datos, como la aproximación sucesiva en el método de Newton) y terminar esta corecursion requiere que los datos eventualmente satisfagan alguna condición, que no está necesariamente garantizada.
  • En términos de variantes de bucle , la recursividad estructural es cuando hay una variante de bucle obvia, a saber, tamaño o complejidad, que comienza finito y disminuye en cada paso recursivo.
  • Por el contrario, la recursividad generativa ocurre cuando no existe una variante de bucle tan obvia, y la terminación depende de una función, como "error de aproximación" que no necesariamente disminuye a cero y, por lo tanto, la terminación no está garantizada sin un análisis adicional.

Problemas de implementación

En la implementación real, en lugar de una función recursiva pura (verificación única para el caso base, de lo contrario paso recursivo), se pueden realizar una serie de modificaciones, con fines de claridad o eficiencia. Éstos incluyen:

  • Función de envoltura (en la parte superior)
  • Cortocircuito del caso base, también conocido como "recursividad a plena competencia" (en la parte inferior)
  • Algoritmo híbrido (en la parte inferior): cambiar a un algoritmo diferente una vez que los datos son lo suficientemente pequeños

Sobre la base de la elegancia, las funciones de envoltura generalmente están aprobadas, mientras que el cortocircuito de la carcasa base está mal visto, particularmente en el mundo académico. Los algoritmos híbridos se utilizan a menudo por motivos de eficiencia, para reducir la sobrecarga de la recursividad en casos pequeños, y la recursividad independiente es un caso especial de esto.

Función de envoltura

Una función contenedora es una función que se llama directamente pero que no recurre a sí misma, sino que llama a una función auxiliar separada que en realidad realiza la recursividad.

Las funciones de envoltura se pueden usar para validar parámetros (para que la función recursiva pueda omitirlos), realizar la inicialización (asignar memoria, inicializar variables), particularmente para variables auxiliares como "nivel de recursividad" o cálculos parciales para memorización , y manejar excepciones y errores. . En los lenguajes que admiten funciones anidadas , la función auxiliar se puede anidar dentro de la función contenedora y utilizar un ámbito compartido. En ausencia de funciones anidadas, las funciones auxiliares son en cambio una función separada, si es posible privada (ya que no se llaman directamente), y la información se comparte con la función contenedora mediante el uso de paso por referencia .

Cortocircuito de la caja base

Factorial: ordinario frente a cortocircuito
Recursividad ordinaria Recursividad de cortocircuito
int fac1(int n) {
   if (n <= 0)
      return 1;
   else
      return fac1(n-1)*n;
}
static int fac2(int n) {
   // assert(n >= 2);
   if (n == 2)
      return 2;
   else
      return fac2(n-1)*n;
}
int fac2wrapper(int n) {
   if (n <= 1)
      return 1;
   else
      return fac2(n);
}

Poner en cortocircuito el caso base, también conocido como recursión de plena competencia , consiste en verificar el caso base antes de realizar una llamada recursiva, es decir, verificar si la siguiente llamada será el caso base, en lugar de llamar y luego verificar el caso base. . El cortocircuito se realiza particularmente por razones de eficiencia, para evitar la sobrecarga de una llamada de función que regresa inmediatamente. Tenga en cuenta que, dado que el caso base ya ha sido verificado (inmediatamente antes del paso recursivo), no es necesario verificarlo por separado, pero sí es necesario usar una función contenedora para el caso en el que la recursividad general comienza con el caso base. sí mismo. Por ejemplo, en la función factorial, ¡correctamente el caso base es 0! = 1, mientras que inmediatamente devuelve 1 por 1! es un cortocircuito y puede perder 0; esto se puede mitigar con una función contenedora. El cuadro muestra el código C para atajar los casos factoriales 0 y 1.

El cortocircuito es principalmente una preocupación cuando se encuentran muchos casos base, como punteros nulos en un árbol, que pueden ser lineales en el número de llamadas a funciones, por lo tanto, ahorros significativos para los algoritmos O ( n ) ; esto se ilustra a continuación para una búsqueda en profundidad. El cortocircuito en un árbol corresponde a considerar una hoja (nodo no vacío sin hijos) como el caso base, en lugar de considerar un nodo vacío como el caso base. Si solo hay un caso base único, como en el cálculo del factorial, el cortocircuito proporciona solo O (1) ahorros.

Conceptualmente, se puede considerar que el cortocircuito tiene el mismo caso base y el mismo paso recursivo, verificando el caso base solo antes de la recursividad, o puede considerarse que tiene un caso base diferente (un paso eliminado del caso base estándar) y un caso base diferente. paso recursivo más complejo, a saber, "comprobar válido y luego recurrente", como al considerar nodos hoja en lugar de nodos nulos como casos base en un árbol. Debido a que el cortocircuito tiene un flujo más complicado, en comparación con la clara separación del caso base y el paso recursivo en la recursividad estándar, a menudo se considera un estilo deficiente, particularmente en el mundo académico.

Búsqueda en profundidad

Un ejemplo básico de cortocircuito se da en la búsqueda en profundidad (DFS) de un árbol binario; vea la sección de árboles binarios para una discusión recursiva estándar.

El algoritmo recursivo estándar para un DFS es:

  • caso base: si el nodo actual es nulo, devuelve falso
  • paso recursivo: de lo contrario, verifique el valor del nodo actual, devuelva verdadero si coincide, de lo contrario, recursivo en los niños

En cortocircuito, esto es en cambio:

  • comprobar el valor del nodo actual, devolver verdadero si coincide,
  • de lo contrario, en los niños, si no es Null, entonces recurre.

En términos de los pasos estándar, esto mueve la verificación del caso base antes del paso recursivo. Alternativamente, estos pueden considerarse una forma diferente de caso base y paso recursivo, respectivamente. Tenga en cuenta que esto requiere una función contenedora para manejar el caso cuando el árbol en sí está vacío (el nodo raíz es Nulo).

En el caso de un árbol binario perfecto de altura h, hay 2 h +1 −1 nodos y 2 h +1 punteros nulos como hijos (2 para cada una de las 2 h hojas), por lo que el cortocircuito corta el número de funciones Llama a la mitad en el peor de los casos.

En C, el algoritmo recursivo estándar se puede implementar como:

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

El algoritmo de cortocircuito se puede implementar como:

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

Tenga en cuenta el uso de la evaluación de cortocircuito de los operadores booleanos && (AND), de modo que la llamada recursiva se realiza solo si el nodo es válido (no nulo). Tenga en cuenta que mientras que el primer término en AND es un puntero a un nodo, el segundo término es un booleano, por lo que la expresión general se evalúa como un booleano. Este es un idioma común en el cortocircuito recursivo. Esto se suma a la evaluación de cortocircuito del booleano || (O) operador, para verificar solo al niño derecho si el niño izquierdo falla. De hecho, todo el flujo de control de estas funciones se puede reemplazar con una sola expresión booleana en una declaración de retorno, pero la legibilidad no sufre ningún beneficio para la eficiencia.

Algoritmo híbrido

Los algoritmos recursivos suelen ser ineficaces para datos pequeños, debido a la sobrecarga de las llamadas y devoluciones de funciones repetidas. Por esta razón, las implementaciones eficientes de algoritmos recursivos a menudo comienzan con el algoritmo recursivo, pero luego cambian a un algoritmo diferente cuando la entrada se vuelve pequeña. Un ejemplo importante es la ordenación por combinación , que a menudo se implementa cambiando a la ordenación por inserción no recursiva cuando los datos son lo suficientemente pequeños, como en la ordenación por combinación en mosaico . Los algoritmos recursivos híbridos a menudo se pueden refinar aún más, como en Timsort , derivados de una ordenación híbrida de combinación / inserción.

Recurrencia versus iteración

La recursividad y la iteración son igualmente expresivas: la recursividad se puede reemplazar por la iteración con una pila de llamadas explícita , mientras que la iteración se puede reemplazar con la recursividad de cola . Qué enfoque es preferible depende del problema que se esté considerando y del lenguaje utilizado. En la programación imperativa , se prefiere la iteración, particularmente para la recursividad simple, ya que evita la sobrecarga de las llamadas a funciones y la gestión de la pila de llamadas, pero la recursividad se usa generalmente para la recursividad múltiple. Por el contrario, en los lenguajes funcionales se prefiere la recursividad, con la optimización de la recursividad de cola que conduce a una pequeña sobrecarga. Es posible que la implementación de un algoritmo mediante iteración no sea fácil de lograr.

Compare las plantillas para calcular x n definido por x n = f (n, x n-1 ) a partir de x base :

function recursive(n)
    if n == base
        return xbase
    else
        return f(n, recursive(n-1))
function iterative(n)
    x = xbase
    for i = base+1 to n
        x = f(i, x)
    return x

Para el lenguaje imperativo, la sobrecarga es definir la función, para el lenguaje funcional, la sobrecarga es definir la variable acumuladora x.

Por ejemplo, una función factorial puede implementarse iterativamente en C asignando a una variable de índice de bucle y una variable de acumulación, en lugar de pasar argumentos y devolver valores por recursividad:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Poder expresivo

La mayoría de los lenguajes de programación que se utilizan hoy en día permiten la especificación directa de funciones y procedimientos recursivos. Cuando se llama a una función de este tipo, el entorno de ejecución del programa realiza un seguimiento de las diversas instancias de la función (a menudo utilizando una pila de llamadas , aunque se pueden utilizar otros métodos). Cada función recursiva se puede transformar en una función iterativa reemplazando las llamadas recursivas con construcciones de control iterativas y simulando la pila de llamadas con una pila gestionada explícitamente por el programa.

A la inversa, todas las funciones y procedimientos iterativos que pueden ser evaluados por una computadora (ver completitud de Turing ) pueden expresarse en términos de funciones recursivas; Las construcciones de control iterativas, como los bucles while y los bucles for, se reescriben rutinariamente en forma recursiva en lenguajes funcionales . Sin embargo, en la práctica, esta reescritura depende de la eliminación de la llamada de cola , que no es una característica de todos los idiomas. C , Java y Python son lenguajes dominantes notables en los que todas las llamadas a funciones, incluidas las llamadas finales , pueden provocar una asignación de pila que no se produciría con el uso de construcciones en bucle; En estos lenguajes, un programa iterativo en funcionamiento reescrito en forma recursiva puede desbordar la pila de llamadas , aunque la eliminación de llamadas finales puede ser una característica que no está cubierta por la especificación de un lenguaje, y las diferentes implementaciones del mismo lenguaje pueden diferir en las capacidades de eliminación de llamadas finales.

Problemas de desempeño

En lenguajes (como C y Java ) que favorecen las construcciones de bucle iterativo, generalmente hay un costo de tiempo y espacio significativo asociado con los programas recursivos, debido a la sobrecarga requerida para administrar la pila y la relativa lentitud de las llamadas a funciones; en lenguajes funcionales , una llamada de función (particularmente una llamada de cola ) es típicamente una operación muy rápida, y la diferencia usualmente es menos notoria.

Como ejemplo concreto, la diferencia de rendimiento entre las implementaciones recursivas e iterativas del ejemplo "factorial" anterior depende en gran medida del compilador utilizado. En los lenguajes donde se prefieren las construcciones en bucle, la versión iterativa puede ser hasta varios órdenes de magnitud más rápida que la recursiva. En lenguajes funcionales, la diferencia de tiempo total de las dos implementaciones puede ser insignificante; de hecho, el costo de multiplicar primero los números más grandes en lugar de los números más pequeños (lo que sucede con la versión iterativa que se proporciona aquí) puede abrumar el tiempo que se ahorra al elegir la iteración.

Espacio de la pila

En algunos lenguajes de programación, el tamaño máximo de la pila de llamadas es mucho menor que el espacio disponible en el montón , y los algoritmos recursivos tienden a requerir más espacio de pila que los algoritmos iterativos. En consecuencia, estos lenguajes a veces imponen un límite a la profundidad de la recursividad para evitar desbordamientos de pila ; Python es uno de esos lenguajes. Tenga en cuenta la advertencia siguiente con respecto al caso especial de recursividad de cola .

Vulnerabilidad

Debido a que los algoritmos recursivos pueden estar sujetos a desbordamientos de pila, pueden ser vulnerables a entradas patológicas o maliciosas . Algunos malware se dirigen específicamente a la pila de llamadas de un programa y se aprovechan de la naturaleza inherentemente recursiva de la pila. Incluso en ausencia de malware, un desbordamiento de pila causado por una recursividad ilimitada puede ser fatal para el programa, y ​​la lógica de manejo de excepciones puede no evitar que se termine el proceso correspondiente .

Multiplica problemas recursivos

Los problemas recursivos múltiples son intrínsecamente recursivos, debido al estado anterior que necesitan rastrear. Un ejemplo es el recorrido del árbol como en la búsqueda en profundidad primero ; aunque se utilizan métodos recursivos e iterativos, contrastan con el recorrido de lista y la búsqueda lineal en una lista, que es un método recursivo simple y, por lo tanto, naturalmente iterativo. Otros ejemplos incluyen algoritmos de divide y vencerás como Quicksort y funciones como la función de Ackermann . Todos estos algoritmos se pueden implementar de forma iterativa con la ayuda de una pila explícita , pero el esfuerzo del programador involucrado en la gestión de la pila y la complejidad del programa resultante superan posiblemente las ventajas de la solución iterativa.

Refactorización de la recursividad

Los algoritmos recursivos se pueden reemplazar con contrapartes no recursivas. Un método para reemplazar algoritmos recursivos es simularlos usando memoria de pila en lugar de memoria de pila . Una alternativa es desarrollar un algoritmo de reemplazo basado completamente en métodos no recursivos, lo que puede ser un desafío. Por ejemplo, los algoritmos recursivos para comodines coincidentes , tales como Rich Salz ' wildmat algoritmo, fueron una vez típico. Se han desarrollado algoritmos no recursivos para el mismo propósito, como el algoritmo de comodines de coincidencia de Krauss , para evitar los inconvenientes de la recursividad y se han mejorado solo gradualmente basándose en técnicas como la recopilación de pruebas y el rendimiento de perfiles .

Funciones recursivas de cola

Las funciones recursivas de cola son funciones en las que todas las llamadas recursivas son llamadas de cola y, por lo tanto, no acumulan operaciones diferidas. Por ejemplo, la función gcd (que se muestra de nuevo a continuación) es recursiva por cola. Por el contrario, la función factorial (también a continuación) no es recursiva en la cola; debido a que su llamada recursiva no está en la posición final, genera operaciones de multiplicación diferidas que deben realizarse después de que se complete la llamada recursiva final. Con un compilador o intérprete que trata las llamadas recursivas de cola como saltos en lugar de llamadas a funciones, una función recursiva de cola como gcd se ejecutará utilizando un espacio constante. Por lo tanto, el programa es esencialmente iterativo, equivalente a usar estructuras de control de lenguaje imperativas como los bucles "for" y "while".

Recursión de cola : Aumento de la recursividad:
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

La importancia de la recursividad de cola es que cuando se hace una llamada recursiva de cola (o cualquier llamada de cola), no es necesario guardar la posición de retorno de la persona que llama en la pila de llamadas ; cuando la llamada recursiva regresa, se ramificará directamente en la posición de retorno previamente guardada. Por lo tanto, en los lenguajes que reconocen esta propiedad de las llamadas de cola, la recursividad de cola ahorra espacio y tiempo.

Orden de ejecución

Considere estas dos funciones:

Función 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

Recursive1.svg

Función 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

Recursive2.svg

La función 2 es la función 1 con las líneas intercambiadas.

En el caso de una función que se llama a sí misma solo una vez, las instrucciones colocadas antes de la llamada recursiva se ejecutan una vez por recursión antes de cualquiera de las instrucciones colocadas después de la llamada recursiva. Estos últimos se ejecutan repetidamente después de que se haya alcanzado la recursividad máxima.

También tenga en cuenta que el orden de las declaraciones de impresión se invierte, lo que se debe a la forma en que las funciones y las declaraciones se almacenan en la pila de llamadas .

Procedimientos recursivos

Factorial

Un ejemplo clásico de procedimiento recursivo es la función utilizada para calcular el factorial de un número natural :

Pseudocódigo (recursivo):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial

La función también se puede escribir como una relación de recurrencia :

Esta evaluación de la relación de recurrencia demuestra el cálculo que se realizaría al evaluar el pseudocódigo anterior:

Calculando la relación de recurrencia para n = 4:
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 se puede describir sin utilizar la recursividad haciendo uso de las típicas construcciones de bucle que se encuentran en los lenguajes de programación imperativos:

Pseudocódigo (iterativo):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial

El código imperativo anterior es equivalente a esta definición matemática usando una variable acumuladora t :

La definición anterior se traduce directamente a lenguajes de programación funcionales como Scheme ; este es un ejemplo de iteración implementada de forma recursiva.

Máximo común divisor

El algoritmo euclidiano , que calcula el máximo común divisor de dos enteros, se puede escribir de forma recursiva.

Definición de función :

Pseudocódigo (recursivo):
function gcd is:
input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd

Relación de recurrencia para el máximo común divisor, donde expresa el resto de :

si
Calculando la relación de recurrencia para x = 27 e y = 9:
gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9
Calculando la relación de recurrencia para x = 111 e y = 259:
gcd(111, 259)   = gcd(259, 111 % 259)
                = gcd(259, 111)
                = gcd(111, 259 % 111)
                = gcd(111, 37)
                = gcd(37, 111 % 37)
                = gcd(37, 0)
                = 37

El programa recursivo anterior es recursivo de cola ; es equivalente a un algoritmo iterativo, y el cálculo que se muestra arriba muestra los pasos de evaluación que realizaría un lenguaje que elimina las llamadas de cola. A continuación se muestra una versión del mismo algoritmo que utiliza iteración explícita, adecuada para un lenguaje que no elimina las llamadas de cola. Al mantener su estado totalmente en las variables x e y y el uso de una construcción de bucle, el programa evita hacer llamadas recursivas y el crecimiento de la pila de llamadas.

Pseudocódigo (iterativo):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called 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 dado el conocimiento del algoritmo euclidiano es más difícil comprender el proceso mediante una simple inspección, aunque los dos algoritmos son muy similares en sus pasos.

Torres de Hanoi

Torres de Hanoi

Las Torres de Hanoi es un acertijo matemático cuya solución ilustra la recursividad. Hay tres clavijas que pueden contener pilas de discos de diferentes diámetros. Un disco más grande nunca puede apilarse encima de uno más pequeño. Comenzando con n discos en una clavija, deben moverse a otra clavija de uno en uno. ¿Cuál es el menor número de pasos para mover la pila?

Definición de función :

Relación de recurrencia para hanoi :

Calculando la relación de recurrencia para n = 4:
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


Implementaciones de ejemplo:

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 Hanoi se puede reducir a una fórmula explícita.

Una fórmula explícita para Towers of Hanoi:
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
In general:
hn = 2n - 1, for all n >= 1

Búsqueda binaria

El algoritmo de búsqueda binaria es un método para buscar en una matriz ordenada un solo elemento cortando la matriz por la mitad con cada pasada recursiva. El truco consiste en elegir un punto medio cerca del centro de la matriz, comparar los datos en ese punto con los datos que se buscan y luego responder a una de las tres condiciones posibles: los datos se encuentran en el punto medio, los datos en el punto medio son mayores que los datos que se buscan, o los datos en el punto medio son menores que los datos que se buscan.

La recursividad se utiliza en este algoritmo porque con cada paso se crea una nueva matriz cortando la antigua por la mitad. El procedimiento de búsqueda binaria se llama entonces de forma recursiva, esta vez en la nueva (y más pequeña) matriz. Normalmente, el tamaño de la matriz se ajusta manipulando un índice de inicio y finalización. El algoritmo exhibe un orden de crecimiento logarítmico porque esencialmente divide el dominio del problema a la mitad con cada pasada.

Implementación de ejemplo de búsqueda binaria en C:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Estructuras de datos recursivas (recursividad estructural)

Una aplicación importante de la recursividad en la informática es la definición de estructuras de datos dinámicas como listas y árboles . Las estructuras de datos recursivas pueden crecer dinámicamente hasta un tamaño teóricamente infinito en respuesta a los requisitos de tiempo de ejecución; por el contrario, el tamaño de una matriz estática debe establecerse en tiempo de compilación.

"Los algoritmos recursivos son particularmente apropiados cuando el problema subyacente o los datos a tratar se definen en términos recursivos".

Los ejemplos de esta sección ilustran lo que se conoce como "recursividad estructural". Este término se refiere al hecho de que los procedimientos recursivos actúan sobre datos que se definen de forma recursiva.

Siempre que un programador derive la plantilla de una definición de datos, las funciones emplean recursividad estructural. Es decir, las recursiones en el cuerpo de una función consumen una parte inmediata de un valor compuesto dado.

Listas vinculadas

A continuación se muestra una definición en C de una estructura de nodo de lista vinculada. Observe especialmente cómo se define el nodo en términos de sí mismo. El elemento "siguiente" del nodo de estructura es un puntero a otro nodo de estructura , creando efectivamente un tipo de lista.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Debido a que la estructura de datos del nodo struct se define de forma recursiva, los procedimientos que operan en ella se pueden implementar de forma natural como procedimientos recursivos. El procedimiento list_print definido a continuación recorre la lista hasta que la lista está vacía (es decir, el puntero de la lista tiene un valor de NULL). Para cada nodo, imprime el elemento de datos (un número entero). En la implementación de C, la lista permanece sin cambios por el procedimiento list_print .

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Árboles binarios

A continuación se muestra una definición simple para un nodo de árbol binario. Al igual que el nodo de las listas vinculadas, se define en términos de sí mismo, de forma recursiva. Hay dos punteros autorreferenciales: izquierdo (apuntando al subárbol izquierdo) y derecho (apuntando al subárbol derecho).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

Las operaciones en el árbol se pueden implementar mediante recursividad. Tenga en cuenta que debido a que hay dos punteros de autorreferencia (izquierda y derecha), las operaciones de árbol pueden requerir dos llamadas recursivas:

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

Como máximo, se realizarán dos llamadas recursivas para cualquier llamada dada a tree_contains como se definió anteriormente.

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

El ejemplo anterior ilustra un recorrido en orden del árbol binario. Un árbol de búsqueda binario es un caso especial del árbol binario donde los elementos de datos de cada nodo están en orden.

Recorrido del sistema de archivos

Dado que la cantidad de archivos en un sistema de archivos puede variar, la recursividad es la única forma práctica de recorrer y así enumerar su contenido. Atravesar un sistema de archivos es muy similar a atravesar un árbol , por lo tanto, los conceptos detrás del cruce de un árbol son aplicables a atravesar un sistema de archivos. Más específicamente, el siguiente código sería un ejemplo de un recorrido de preorden de un sistema de archivos.

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

Este código es tanto recursivo como iterativo : los archivos y directorios se iteran y cada directorio se abre de forma recursiva.

El método "rtraverse" es un ejemplo de recursividad directa, mientras que el método "traverse" es una función contenedora.

El escenario del "caso base" es que siempre habrá un número fijo de archivos y / o directorios en un sistema de archivos determinado.

Eficiencia en el tiempo de los algoritmos recursivos

La eficiencia del tiempo de algoritmos recursivos se puede expresar en una relación de recurrencia de Big O notación . Luego (generalmente) se pueden simplificar en un solo término Big-O.

Regla de acceso directo (teorema maestro)

Si la complejidad temporal de la función tiene la forma

Entonces el Big O de la complejidad del tiempo es así:

  • Si por alguna constante , entonces
  • Si entonces
  • Si para alguna constante , y si para alguna constante c <1 y todas n suficientemente grandes , entonces

donde a representa el número de llamadas recursivas en cada nivel de recursividad, b representa en qué factor menor es la entrada para el siguiente nivel de recursividad (es decir, el número de piezas en las que divide el problema), y f  ( n ) representa el trabajo la función es independiente de cualquier recursividad (por ejemplo, particionamiento, recombinación) en cada nivel de recursividad.

Ver también

Notas

Referencias