Algoritmos Recursivos

Unidad 3 Algoritmos Recursivos

Introducción

Recursión:
Proceso de resolver un problema grande descomponiéndolo en uno o más
subproblemas que son de estructura idéntica a la del problemaoriginal y mas subproblemas que son de estructura idéntica a la del problema original y más simples de resolver que el problema original. Cada subproblema se resuelve de forma similar, repitiendo ladescomposición hasta generar subproblemas tan simples que se resuelven sin necesidad de descomponerlos.

La solución del problema original se obtiene combinando las soluciones de los
subproblemas enun proceso inverso a la descomposición realizada.

La recursividad es una propiedad de la estrategia para resolver un
problema y no del problema en sí.

Definición

Algoritmo recursivo:procedimiento que se invoca a sí mismo, debe parar al ingresar una instancia simple de resolver.

Clasificación

i) Directa: en algún paso del conjunto de instrucciones aparece una invocación alpropio procedimiento. llamada a P Procedimiento P
ii) Indirecta: el procedimiento llama a otro procedimiento, éste a su vez llama al primero. Asimismo, si un procedimiento llama a otros y, en algúnmomento, alguno de éstos llama al primero también estamos frente a recursión indirecta.
En toda definición recursiva de un problema se debe establecer una condición de borde, es decir, una condición queno requiera otra definición recursiva para resolverse. Esta determina el criterio de parada del algoritmo recursivo.
Ventajas e Inconvenientes
Ventajas
-No es necesario definir la secuencia depasos exacta para resolver el problema.
-Soluciones simples, claras.
-Soluciones elegantes.
-Soluciones a problemas complejos.

Inconvenientes
-Podría ser menos eficiente.
-Sobrecarga asociadacon las llamadas a subalgoritmos
-Una simple llamada puede generar un gran número de llamadas recursivas. (Fact (n) generan llamadas recursivas)
-¿La claridad compensa la sobrecarga?
-El valor...