RECURSIVIDAD

RECURSIVIDAD

CONCEPTO
1. 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
1. La recursividad debe terminar alguna vez: caso base
2. Cada nueva formulación estamos más cerca del caso final (o base).
3. Las funciones recursivas son útiles para “recorrer” estructuras anidadas, como árboles.
TIPOS
1. 1. SIMPLE
    1. Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos , ejemplo el factorial
      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));}
  2. ANIDADA
    1. En algunos de los arg. de la llamada recursiva hay una nueva llamada a sí misma
      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)));}
  3. MULTIPLE
    1. 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
      1. int Fib( int n ) /* ej: Fibonacci */{if(n<=1) return(1);return(Fib(n-1) + Fib(n-2));}
ventajas
1. Soluciones simples, claras.
2. Soluciones elegantes.
3. Soluciones a problemas complejos.
Desventajas
1. Sobrecarga asociada con las llamadas a subalgoritmos
2. Una simple llamada puede generar un gran número de llamadas recursivas. (Fact(n) genera n llamadas recursivas)
3. El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fácil solución iterativa.

Nächster

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von Maria Betancourt vor etwa 4 Jahre