Recursión (informática)
En informática , la recursividad es un método para resolver un problema en el que la solución depende de soluciones a instancias más pequeñas del mismo problema. [1] 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. [2]
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.
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 funcional (por ejemplo, Clojure ) [4] no definen ninguna construcción de bucle sino que se basan únicamente en la recursividad para llamar al código repetidamente. Está probado 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 . [ 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 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 y incurrir en tiempo de cálculo adicional), se puede denominar 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 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 denomina "caso de terminación".
