Definición de Función recursiva
Tipo de función en programación que se caracteriza porque puede llamarse a sí misma durante su ejecución. A diferencia de una función común, que es invocada desde otra función o desde el programa principal, una función recursiva se invoca a sí misma, ya sea de manera directa (se llama a sí misma explícitamente) o indirecta (llama a otra función que a su vez la llama de nuevo).
Las funciones recursivas son especialmente útiles para resolver problemas que pueden dividirse en subproblemas más pequeños y similares al problema original. Ejemplos típicos incluyen el cálculo de factoriales, la secuencia de Fibonacci, el recorrido de árboles y la resolución de problemas de tipo "divide y vencerás", como la búsqueda binaria o el algoritmo de ordenamiento quicksort.
Ejemplo de recursión directa:
- El cálculo del factorial de un número n, donde n! = n * (n-1)!, hasta llegar al caso base 1! = 1.
Ejemplo de recursión indirecta:
- Función A llama a función B, y función B vuelve a llamar a función A, creando un ciclo recursivo.
Para evitar la recursión infinita (bucle infinito), toda función recursiva debe tener una condición de terminación clara, conocida como caso base. El caso base es una condición que, cuando se cumple, hace que la función deje de llamarse a sí misma y retorne un valor concreto. Si no existe un caso base o no se alcanza nunca, el programa puede consumir toda la memoria de la pila de llamadas y terminar en un error de desbordamiento (stack overflow).
Cada llamada recursiva utiliza memoria adicional en la pila de llamadas. Por este motivo, las funciones recursivas pueden ser menos eficientes en cuanto a consumo de memoria que una solución iterativa, especialmente si la recursión es muy profunda.
Ejemplo de una función recursiva
A continuación, un ejemplo clásico de función recursiva para calcular el factorial de un número entero:
int factorial(int numero)
{
if (numero == 1)
return 1; // Caso base
else
return numero * factorial(numero - 1); // Llamada recursiva
}
Por ejemplo, al llamar factorial(5):
- factorial(5) llama a factorial(4)
- factorial(4) llama a factorial(3)
- factorial(3) llama a factorial(2)
- factorial(2) llama a factorial(1)
- factorial(1) retorna 1 (caso base)
Luego, los resultados se van multiplicando hacia atrás: 2 * 1, 3 * 2, 4 * 6, 5 * 24, hasta obtener 120.
Ventajas de las funciones recursivas
- Código más legible y conciso: Permiten expresar soluciones de manera clara y elegante, especialmente en problemas naturalmente recursivos.
- Facilitan la resolución de problemas complejos: Son ideales para problemas que se pueden dividir en subproblemas similares, como el recorrido de árboles o algoritmos matemáticos.
Desventajas de las funciones recursivas
- Mayor consumo de memoria: Cada llamada recursiva ocupa espacio en la pila de llamadas, lo que puede llevar a errores si la recursión es muy profunda.
- Riesgo de recursión infinita: Si no se define correctamente el caso base, la función puede llamarse a sí misma indefinidamente.
- Menor eficiencia en algunos casos: En ciertos problemas, la versión iterativa puede ser más eficiente en cuanto a tiempo y uso de recursos.
Comparación con funciones iterativas
- Recursiva: Más simple y legible para problemas como el recorrido de árboles o la resolución de fractales.
- Iterativa: Más eficiente en consumo de memoria y, en muchos casos, en velocidad de ejecución para problemas lineales o simples.
¿Cuándo usar funciones recursivas?
- Cuando el problema puede dividirse en subproblemas similares al original.
- Cuando la solución iterativa es demasiado compleja o difícil de entender.
- Cuando se trabaja con estructuras de datos como árboles o grafos.
¿Cómo evitar el bucle infinito en funciones recursivas?
Es fundamental definir un caso base claro y asegurarse de que cada llamada recursiva avance hacia ese caso base. Por ejemplo, en el cálculo del factorial, el caso base es cuando el número es igual a 1.
Limitaciones de las funciones recursivas
- Consumo elevado de memoria en recursiones profundas.
- Riesgo de errores por desbordamiento de pila si la recursión no termina.
- Puede ser menos eficiente que una solución iterativa en algunos casos.
¿Es siempre necesario usar funciones recursivas?
No siempre es necesario. En muchos casos, una solución iterativa puede ser más eficiente y sencilla de implementar. La elección entre recursión e iteración depende de la naturaleza del problema y de la claridad del código resultante.
En resumen, una función recursiva es una herramienta poderosa en programación, útil para resolver problemas complejos y para trabajar con estructuras de datos como árboles o listas enlazadas. Sin embargo, debe usarse con precaución y siempre asegurando la existencia de un caso base para evitar bucles infinitos y problemas de memoria.
Autor: Leandro Alegsa
Actualizado: 06-07-2025
¿Cómo citar este artículo?
Alegsa, Leandro. (2025). Definición de Función recursiva. Recuperado de https://www.alegsa.com.ar/Dic/funcion_recursiva.php