Recursividad.
Un programa o
subprograma que se llama a si mismo se dice que es recursivo.
El concepto de
recursividad está ligado, en los lenguajes de programación, al concepto de procedimiento o función. Un
procedimiento o función es recursivo cuando
durante una invocación a él puede ser invocado a su vez él mismo.
La recursividad es
una de las formas de control más importantes en la programación. Los procedimientos recursivos
son la forma más natural de representación
de muchos algoritmos.
Un razonamiento
recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el
punto tanto de partida como de terminación
de la definición.
Tipos de Recursividad.
Recursión Directa e Indirecta.
Directo:
El
subprograma se llama directamente a si mismo.
Indirecta:
Un programa llama a otro subprograma y este a su vez al primero
Recursividad Infinita
Es muy importante
que toda función recursiva tenga un caso
en el que no se llame a sí misma, o
las llamadas serían
infinitas y el programa no tendría fin.
Por eso, siempre
una función recursiva tiene una condición inicial en la que no debe llamarse a
sí misma.
Diferencias entre recursión e iteración.
La recursividad y la
iteración (ejecución en bucle) están muy relacionadas, cualquier acción que
pueda realizarse con la recursividad puede realizarse con iteración y
viceversa. Normalmente, un cálculo determinado se prestará a una técnica u
otra, sólo necesita elegir el enfoque más natural o con el que se sienta más
cómodo.
Tanto la iteración
como la recursión se basan en una estructura de control:
- La iteración
utiliza una estructura repetitiva
- La recursión
utiliza una estructura de selección.
La iteración y la
recursión implican ambas repetición:
- La iteración
utiliza explícitamente una estructura repetitiva
- La recursión
consume la repetición mediante llamadas repetidas.
La iteración y la
recursión implican cada una un test mientras que la recursión termina cuando se reconoce un caso base o la
condición de salida se alcanza.
Ventajas y desventajas.
Ventajas de la Recursión.
- Soluciones simples,
claras
- Soluciones
elegantes.
- Soluciones a
problemas complejos.
Desventajas de la Recursión:
- INEFICIENCIA
-Sobrecarga asociada
con las llamadas a subalgoritmos
Una simple llamada
puede generar un gran número de llamadas recursivas. (Fact(n) genera n llamadas
recursivas)
¿La claridad compensa
la sobrecarga?
El valor de la
recursividad reside en el hecho de que se puede usar para resolver problemas
sin fácil solución iterativa.
- La ineficiencia
inherente de algunos algoritmos recursivos.
La recursividad se
debe usar cuando sea realmente necesaria, es decir, cuando no exista una
solución iterativa simple.
