27198944
Description
Mind Map by Maria Betancourt, updated more than 1 year ago
|
Created by Maria Betancourt
over 3 years ago
|
|
RECURSIVIDAD
- CONCEPTO
- Se llama recursividad a un proceso mediante el que una función se llama a sí misma de
forma repetida, hasta que se satisface alguna determinada condición. El proceso se
utiliza para computaciones repetidas en las que cada acción se determina mediante un
resultado anterior. Se pueden escribir de esta forma muchos problemas iterativos.
- Se llama recursividad a un proceso mediante el que una función se llama a sí misma de
forma repetida, hasta que se satisface alguna determinada condición. El proceso se
utiliza para computaciones repetidas en las que cada acción se determina mediante un
resultado anterior. Se pueden escribir de esta forma muchos problemas iterativos.
- CARACTERISTICAS
- La recursividad debe
terminar alguna vez: caso
base
- Cada nueva formulación
estamos más cerca del caso final
(o base).
- Las funciones recursivas son útiles para
“recorrer” estructuras anidadas, como
árboles.
- La recursividad debe
terminar alguna vez: caso
base
- TIPOS
- SIMPLE
- Aquella en cuya
definición sólo aparece
una llamada recursiva.
Se puede transformar
con facilidad en
algoritmos iterativos ,
ejemplo el factorial
- Ej: Par o Impar: int par( int
nump ) { if(nump==0)
return(1); return(
impar(nump-1)); } int impar( int
numi ) { if(numi==0)
return(0); return( par(numi-1)); }
- Ej: Par o Impar: int par( int
nump ) { if(nump==0)
return(1); return(
impar(nump-1)); } int impar( int
numi ) { if(numi==0)
return(0); return( par(numi-1)); }
- Aquella en cuya
definición sólo aparece
una llamada recursiva.
Se puede transformar
con facilidad en
algoritmos iterativos ,
ejemplo el factorial
- ANIDADA
- En algunos de los arg. de la
llamada recursiva hay una
nueva llamada a sí misma
- int Ack( int n, int m ) /*
ej: Ackerman */ { if(n==0
) return(m+1); else
if(m==0)
return(Ack(n-1,1)); return(Ack(n-1,
Ack(n,m-1))); }
- int Ack( int n, int m ) /*
ej: Ackerman */ { if(n==0
) return(m+1); else
if(m==0)
return(Ack(n-1,1)); return(Ack(n-1,
Ack(n,m-1))); }
- En algunos de los arg. de la
llamada recursiva hay una
nueva llamada a sí misma
- MULTIPLE
- Es cuando hay más de
una llamada a sí
misma dentro del
cuerpo de la función,
resultando más difícil
de hacer de forma
iterativa
- int Fib( int n ) /* ej:
Fibonacci */ { if(n<=1)
return(1); return(Fib(n-1)
+ Fib(n-2)); }
- int Fib( int n ) /* ej:
Fibonacci */ { if(n<=1)
return(1); return(Fib(n-1)
+ Fib(n-2)); }
- Es cuando hay más de
una llamada a sí
misma dentro del
cuerpo de la función,
resultando más difícil
de hacer de forma
iterativa
- SIMPLE
- ventajas
- Soluciones simples, claras.
- Soluciones elegantes.
- Soluciones a problemas complejos.
- Soluciones simples, claras.
- Desventajas
- 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)
- El valor de la recursividad reside en el hecho de que se puede
usar para resolver problemas sin fácil solución iterativa.
- Sobrecarga asociada con las llamadas a subalgoritmos
Want to create your own Mind Maps for free with GoConqr? Learn more.