Recursividad

Estructuras de datos |
Recursividad |
Instituto Tecnológico De Chihuahua II |
|
|
|

|
08/11/2010

“El software es conocimiento y tanto el software como el conocimiento deben ser libres”

Indice

Introducción 4

Recursividad 5

Tipos de recursividad 6

Procedimientos recursivos 7

Mecánica de la recursividad 8Transformacion de algoritmos iterativos a recursivos 9

Recursividad en el diseño 12

Complejidad en los algoritmos recursivos 13

Conclusiones 14
Blibliografías 14

Introducción

El área de la programación es muy amplia y con muchos detalles. Los programadores necesitan ser capaces de resolver todos los problemas que seles presente a través del computador aun cuando en el lenguaje que utilizan no haya una manera directa de resolver los problemas. En el lenguaje de programación C, así como en otros lenguajes de programación, se puede aplicar una técnica que se le dio el nombre de recursividad por su funcionalidad. Esta técnica es utilizada en la programación estructurada para resolver problemas que tengan que vercon el factorial de un número, o juegos de lógica. Las asignaciones de memoria pueden ser dinámicas o estáticas y hay diferencias entre estas dos y se pueden aplicar las dos en un programa cualquiera.

Recursividad
Es una Técnica que permite que una función se llame a si misma. El concepto de Recursividad va ligado a la repetición.
Son Recursivos aquellos algoritmos que, estando encapsuladosdentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos que hacen uso de bucles while, do-while, for, etc.
Para que una función recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado. En un algoritmo recursivo distinguimos como mínimo 2 partes:
a). Caso trivial, base o fin derecursión: Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.
b). Parte puramente recursiva: Relaciona el resultado del algoritmo con resultados de casos mas simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.
Ejemplos:
Iterativo:Recursivo:
int Factorial (int n){ int Factorial(int n){
int i, res = 1; if(n==0) return 1;
for(i = 1, i<=n; i++) return( n*Factorial(n-1));
res = res*I; }
return res;
}

Tipos de recursividad
Recursividad Simple: Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformarcon facilidad en algoritmos iterativos.
Recursividad Múltiple: Se da 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.
ejemplo: Fibonacci
int Fib( int n ) {
if(n<=1) return(1);
return(Fib(n-1) + Fib(n-2)); }
Recursividad Anidada: En algunos de los argumentos de la llamada recursiva hay una nueva llamada a símisma.
ejemplo: Ackerman
int Ack( int n, int m ) {
if(n==0 ) return(m+1);
else if(m==0) return(Ack(n-1,1));
return(Ack(n-1, Ack(n,m-1))); }
Recursividad cruzada o indirecta: Son algoritmos donde una función provoca una llamada a sí misma de forma indirecta, a través de otras funciones.
Ejemplo: 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)); }

Procedimientos recursivos
Un procedimiento recursivo es aquél que se llama a sí mismo.
Consideraciones sobre procedimientos recursivos:
Condiciones de limitación: Debe designar un procedimiento recursivo para probar al menos una condición que pueda poner fin a la recursividad; también debe supervisar los casos en...