recursión

La recursión es un método en el que un objeto o problema se define a partir de sí mismo. En matemáticas y ciencias de la computación, una definición recursiva describe un objeto dividiéndolo en subobjetos del mismo tipo y, para ser válida, requiere un caso base que ponga fin a la repetición. En programación, una función recursiva se llama a sí misma con un estado reducido del problema y, cuando se alcanza el caso base, se devuelven los resultados acumulados.

Un ejemplo clásico es el factorial: n! = n × (n−1)!, con la base 0! = 1. Otro ejemplo es la secuencia de Fibonacci, que puede definirse recursivamente como F(n) = F(n−1) + F(n−2) y F(0) = 0, F(1) = 1; su implementación simple es exponencial sin optimización. En la práctica, la recursión se usa en algoritmos de divide y vencer, búsqueda binaria recursiva o recorrido de estructuras jerárquicas. En algunos lenguajes se puede optimizar mediante la recursión de cola, que facilita la compilación a bucles, aunque no todos los lenguajes la implementan.

La recursión también se estudia en términos formales mediante relaciones de recurrencia que describen secuencias o el coste de algoritmos. Sus ventajas incluyen claridad y expresividad para problemas naturalmente anidados; sus desventajas son la posible profundidad de pila y consumo de memoria, y en algunos casos menor eficiencia respecto a soluciones iterativas. En otros campos, la idea de recursión aparece en lingüística y teoría de grafos como forma de describir estructuras que se anidan o se descomponen a sí mismas.