Tod ist unvermeidlich, aber meist unbedeutend...

martes, 19 de marzo de 2013

Recursividad

Hola que tal, en esta ocasión vamos a hablar de la Recursión. La Recursión es como un circulo sin fin, un claro ejemplo de esto es la siguiente imagen:


Anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, de forma recursiva. (Tomado de Wikipedia)
Con la programación podemos hacer lo mismo, por ejemplo si queremos calcular el factorial de un número lo podemos hacer de forma recursiva. Tal vez sea un poco confuso si es la primera vez que escuchan hablar de este termino, pero es muy sencillo.

Vamos a hacer un programa el cuál use funciones que se llamen a si mismas. ¿Es esto posible? Si en efecto es posible. Pero, ¿El programa no terminará nunca? En efecto, seria un ciclo sin fin, pero para ello usaremos en base a un razonamiento cual será la condición para la cuál se deje de hacer la llamada a si mismo.

Y creo que esto no quedará claro hasta que se pueda visualizar en un ejemplo, por ejemplo queremos realizar la suma para n=5
Esto es: 1+2+3+4+5=15

Veamos el razonamiento:
sumaRecursiva(1)=1
sumaRecursiva(2)=sumaRecursiva(1)+2 = 3
sumaRecursiva(3)=sumaRecursiva(2)+3 = 3 + 3 = 6
sumaRecursiva(4)=sumaRecursiva(3)+4 = 6 + 4 = 10
sumaRecursiva(5)=sumaRecursiva(4)+5 = 10 + 5 = 15
.....
.....
.....
De forma general sería:
sumaRecursiva(n) = sumaRecursiva(n-1)+n ----> Para n>1
Si n=1 ---> sumaRecursiva(1)=1

Si lo programamos de forma iterativa sería algo como:
public int sumaIterativa(int m){
    int n=0,i;
    for(i=1;i<=m;i++)
        n+=i;
    return n;
}
Pero si lo hacemos de forma recursiva sería algo como:

public int sumaRecursiva(int n){
    if(n==1)
        return 1;
    return sumaRecursiva(n-1)+n;
}

Lenguaje empleado: Java. Ambos códigos realizan lo mismo pero están programados de formas diferentes, el primero es simple usando un ciclo for se realiza la sumas hasta que se alcance al valor deseado, en la segunda forma se llama a si mismo, y dejará de llamarse hasta que el valor de n sea igual a 1. Esta es la condición para que la recursividad se rompa.

Un ejemplo de la serie de Fibonacci usando recursividad en Lenguaje Python:
def fibonacci(n):
    if((n==1) or (n==2)):
        return 1
    else:
        return (fibonacci(n-1)+fibonacci(n-2))
n=int(input("Numero: "))
print ("Resultado: %d"%fibonacci(n))

Eso es todo, un Saludo.
Loki!

0 comentarios:

Publicar un comentario