Recursividad (ciencias de la computación)
En informática , 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. [1] Tales 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 tales problemas recursivos 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. [2]
Evidentemente, el poder de la recursividad reside 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.
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 ) [4] no definen ninguna construcción de bucle, sino que se basan únicamente en la recursividad para llamar repetidamente al código. Está demostrado en la teoría de la computabilidad que estos lenguajes solo recursivos son Turing completos ; esto significa que son tan poderosos (pueden usarse para resolver los mismos problemas) como 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 llamada de cola . [ cita requerida ]
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 divide y vencerás ; cuando se combina con una tabla de búsqueda que almacena los resultados de subproblemas resueltos previamente (para evitar resolverlos repetidamente e incurrir en tiempo de cálculo adicional), puede denominarse programación dinámica o memorización .
Una definición de función recursiva tiene uno o más casos base , es decir, entradas para las cuales la función produce un resultado de forma trivial (sin recurrencia), y uno o más casos recursivos , es decir, entradas para las cuales el programa recurre (se llama a sí mismo) . Por ejemplo, la función factorial se puede definir recursivamente mediante las ecuaciones 0! = 1 y, para todo n > 0 , n ! = norte ( norte - 1)!. Ninguna ecuación por sí misma 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 final".
