Significado de Recursividad
Sustantivo femenino. Del latín recursus, «regreso, vuelta atrás», más el sufijo -idad.
La recursividad es la técnica de programación por la que una función se llama a sí misma para resolver versiones más pequeñas de un mismo problema, hasta alcanzar un caso base que detiene las llamadas.
Se usa como alternativa a los bucles cuando un problema puede definirse de forma natural en términos de una versión más simple de sí mismo.
Qué es la recursividad
Una función recursiva se define, al menos en parte, en términos de sí misma: para resolver un problema de tamaño N, la función resuelve primero un problema idéntico pero más pequeño, de tamaño N menos uno, y usa ese resultado para construir la solución completa. Cada llamada genera una nueva llamada, hasta que se alcanza un caso tan sencillo que puede resolverse sin volver a llamarse: el caso base.
Sin un caso base bien definido, una función recursiva se llamaría a sí misma indefinidamente, hasta agotar la memoria reservada para gestionar esas llamadas y detenerse con un error. Por eso toda función recursiva bien escrita necesita dos partes: el caso base, que da una respuesta directa, y el caso recursivo, que reduce el problema y se apoya en una llamada a la propia función.
La estudian la programación y las ciencias de la computación, en temas como el diseño de algoritmos y las estructuras de datos, porque muchos problemas —recorrer árboles, dividir un problema en partes más pequeñas— se expresan de forma más clara con recursividad que con otras técnicas.
Origen de la palabra recursividad
Del latín recursus, «regreso, acción de volver atrás», participio del verbo recurrere, formado por re-, «hacia atrás», y currere, «correr»; más el sufijo -idad, que forma sustantivos abstractos de cualidad. El sentido literal —«volver a recorrer un mismo camino»— refleja bien la idea de una función que vuelve a llamarse a sí misma.
El concepto llegó a la informática desde la lógica matemática y las funciones recursivas estudiadas a comienzos del siglo XX, antes incluso de que existieran los computadores modernos. Con el desarrollo de los lenguajes de programación que permitían que una función se llamara a sí misma, el término pasó a designar también esa técnica concreta de programación.
Elementos de una función recursiva
| Elemento | En qué consiste |
|---|---|
| Caso base | La condición más simple, que se resuelve directamente sin volver a llamar a la función. |
| Caso recursivo | La parte que reduce el problema a una versión más pequeña y se llama a sí misma con esa versión. |
| Pila de llamadas | La estructura de memoria que guarda cada llamada pendiente, hasta que el caso base empieza a resolverlas. |
Se distingue también entre recursividad directa, cuando una función se llama a sí misma, y recursividad indirecta o mutua, cuando dos o más funciones se llaman entre ellas formando un ciclo que termina en algún caso base común.
Ejemplos de uso de recursividad
El cálculo del factorial de un número es el ejemplo más citado para explicar la recursividad.
La función recorre el árbol de carpetas con recursividad, llamándose a sí misma en cada subcarpeta.
El programa entró en un bucle infinito porque la función recursiva no tenía definido ningún caso base.
El profesor explicó la recursividad con el ejemplo de dos espejos enfrentados que se reflejan uno a otro.
Algunos algoritmos de ordenación, como el que divide una lista en mitades sucesivas, se basan en la recursividad.
Sinónimos y palabras relacionadas
Sinónimos: recursión (forma también usada, sobre todo en textos técnicos).
Antónimos: iteración, proceso iterativo.
No es lo mismo que:
- Iteración: repite un bloque de instrucciones mediante un bucle, sin que la función se llame a sí misma; muchos problemas pueden resolverse con recursividad o con iteración, según el caso.
- Bucle: es la estructura que repite instrucciones un número determinado de veces o mientras se cumpla una condición; la recursividad logra un efecto de repetición, pero mediante llamadas a una función, no mediante un bucle.
- Algoritmo: es la secuencia de pasos que resuelve un problema; la recursividad es una técnica concreta con la que puede escribirse ese algoritmo.
Preguntas frecuentes sobre recursividad
¿Qué es el caso base en una función recursiva?
Es la condición más sencilla del problema, la que se resuelve directamente sin necesidad de que la función vuelva a llamarse a sí misma. Sin él, las llamadas no tendrían forma de detenerse.
¿Cuál es la diferencia entre recursividad e iteración?
La recursividad resuelve un problema mediante una función que se llama a sí misma con una versión más pequeña del problema; la iteración lo resuelve repitiendo instrucciones dentro de un bucle, sin llamadas adicionales a ninguna función.
¿Es mejor usar recursividad o un bucle?
Depende del problema: la recursividad suele expresar con más claridad soluciones que se definen de forma natural en partes más pequeñas, como recorrer estructuras jerárquicas, mientras que un bucle puede resultar más eficiente en el uso de memoria.