Facebook Twitter RSS Reset

Recursividad: Teoría

Hola que tal el día de hoy les traigo la siguiente información que los sera de gran ayuda en la programación como Estructura de datos.

Se dice que un método es recursivo si dentro del cuerpo del método contiene llamadas o invocaciones a si mismo. Un método recursivo tendría la siguiente estructura:



metodorecursivo(…)

{ …

metodorecursivo(…); //llamada recursiva

}

Esto implica que una llamada al método recursivo puede generar una o más invocaciones al mismo método, que a su vez genera otras invocaciones, y así sucesivamente.

Un ejemplo son las famosas muñequitas rusas tradicionales llamadas Matrushka cuya características es que están huecas y en su interior guardan otra muñequita de menor tamaño, hasta llegar a la más pequeña.

Recursividad: Teoría

un ejemplo sencillo de un metodo recursivo en codigo c# es sacar sacar el numero vectorial.

public int factorial(int n)

{

if(n > 1)

return n*factorial(n-1)

else

return 1;

}

Como ejemplo si usamos el n= 3 va a entrar al método va a ver si es mayor que el 1 como es verdadero va a regresar el valor de 3 y va a llamar nuevamente el 3 – 1 = 2 .. cuando vuelve a dar por segunda vez n ahora va hacer igual a 2, va a ver nuevamente en las condicionales y va a regresar el valor de n =2 y lo va a restar quedando n=1 con la ultima vuelta va a regresar 1. y ahora va a hacer el proceso a culminar el método recursivo teniendo todos los valores que van a hacer 1*2*3 que va a hacer igual a 6 con lo que termina.



Que debe de cumplir una función recursiva

• Existe una salida no recursiva del procedimiento o función y funciona correctamente en ese caso.

• Cada llamada al procedimiento o función se refiere a un caso más pequeño del mismo.

• Funciona correctamente todo el procedimiento o función recursiva.

Partes que consta un proceso recursivo

• Ley de recurrencia. El subprograma debe realizar una llamada al mismo subprograma, teniendo en cuenta que el valor de los parámetros debera cambiar en cada llamada.

• Condición de salida o caso base. El caso base (condición de salida o parada) es el caso más simple conocido y es el que determinará el fin de la recursividad.

Como construir una función recursiva.

1. Primero, obtener una definición exacta del problema.

2. A continuación, determinar el tamaño del problema completo a resolver. Así se determinarán los valores de los parámetros en la llamada inicial al procedimiento o función.

3. Tercero, resolver el caso base en el que problema puede expresarse no recursivamente. Esto asegurará que se cumple el punto 1 del test anterior.

4. Por último, resolver correctamente el caso general, en términos de un caso más pequeño del mismo problema (llamada recursiva). Esto asegurará cumplir con los puntos 2 y 3.

Ejemplo

public double potencia (double X, int n)

{

if (n==0)

return 1;

else

return (X * potencia(X, n-1));

}

Recursividad: Teoría

No comments yet.

Leave a Comment