Recursion

Un proceso recursivo es aquel en el que los objetos se definen en términos de otros objetos del mismo tipo. Utilizando algún tipo de relación de recurrencia , la clase entera de objetos puede ser construido a partir de unos valores iniciales y un pequeño número de reglas. Los números de Fibonacci se define casi siempre de forma recursiva. Cuidado, sin embargo, se deben tomar para evitar la auto-repetición , en la que un objeto se define en términos de sí mismo, dando lugar a un infinito de anidación.

Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

Factorial — n! = n × (n-1)!

Sucesión de Fibonacci — f(n) = f(n-1) + f(n-2)

Recursion y explicacion ….

}X = 3 //Queremos 3!, por lo tanto X inicial es 3

X >= 2 -> return 3*factorial(2);

X = 2 //Ahora estamos solicitando el factorial de 2

X >= 2 -> return 2*factorial(1);

X = 1 // Ahora estamos solicitando el factorial de 1

X < 2 -> return 1;

/*[En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados]*/

return 2 [es decir: return 2*1 = return 2*factorial(1)]

return 6 [es decir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6

Es decir, que este algoritmo es muy lento. Por ejemplo, para calcular f50 este algoritmo requiere efectuar 20.365.011.073 sumas.

Codigo sin recursion….

int factorial(int x)

{

if (x > -1 && x < 2) return 1; // Cuando -1 < x < 2 devolvemos 1 puesto que 0! = 1 y 1! = 1

else if (x < 0) return 0; // Error no existe factorial de números negativos

return x * factorial(x – 1); // Si x >= 2 devolvemos el producto de x por el factorial de x – 1

😀

#include<stdio.h>
main()
{
int i,n1,n2,n3,a;
printf(“cuantos numeros de la serie fibonacci deseas”);
scanf(“%d”,&i);
n1=0;
n2=1;
if(i==2){
printf(“%d,%d”,n,n2);
}
else{
printf(“%d,%d”,n1,n2);
i=i-3;
for(a=2;a<=i;a=a+1){
n3=n1+n2;
printf(“,%d”,n3);
n1=n2;
n2=n3;
}
}
}

en otras palabras el uso de recursion en la serie fibonacci menos eficiente ya que se ocupa mas cantidad de memoria en bits.

Referencias

http://mathworld.wolfram.com/Recursion.html

http://es.wikipedia.org/wiki/Recursi%C3%B3n

http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci

1 comentario (+¿añadir los tuyos?)

  1. Elisa Schaeffer
    Jul 07, 2011 @ 13:40:23

    Bien; 5.

    Responder

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: