Recursividad

La recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, en otras palabras podríamos definirlo así:

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 Una de las principales ventajas de la recursividad es la resolución de problemas complejos que realizados sin implementar recursividad podría llevarnos tiempos de ejecución demasiado complejos, esta técnica proporciona una forma natural de diseñar algoritmos eficientes y una de sus grandes ventajas es el uso efectivo de la caché. La razón es que una vez que un subproblema es lo suficientemente pequeño, él y todos sus subproblemas se pueden, en principio, solucionar dentro de esa caché, sin tener acceso a la memoria principal, que es mucho más lenta.
Sin embargo también presenta desventajas debido a la lentitud en la ejecución de los proceso recursivo otra de sus desventajas importante, es la dificultad o incluso inconveniencia de aplicar el método a situaciones en las que la solución al problema general no se deriva de la suma directa y simple de los subproblemas (partes) y además la redundancia (algunas soluciones recursivas resuelven un problema en repetidas
Es importante usar recursividad cuando queremos simplificar código y cuando estamos implementando estructuras repetitivas como árboles, si bien es cierto no siempre será útil tal es el caso cuando los métodos usen arreglos largos o cuando el método cambia de manera impredecible de campos y por supuesto cuando las iteraciones sean la mejor opción.
El coste T(n) (en caso peor, medio o mejor) de un algoritmo recursivo, satisface una ecuación recurrente. Esto quiere decir que T(n) dependerá del valor de T para valores más pequeños de n.
Con frecuencia la recurrencia adopta una de las formas siguientes:
1. T(n) = aT(n − c) + g(n), con a y c constantes tales que a > 0 y c > 1
Ejemplo:
1! = 1=1 * 1 = 1 * 0!
¨2! = 2 = 2 * 1 = 2 * 1!
¨3! = 6 = 3 * 2 = 3 * 2!
¨4! = 24= 4 * 6 = 4 * 3!
¨5! = 120= 5 * 24 = 5 * 4!
¨...N! = N * (N – 1)!

función recursiva
factorial (int n)
comienza
si n = 0 entonces regresa 1
otro
regresa factorial (n-1)*n
termina
En mi opinión la recursión se trata de: "Como dice el refrán: divide y vencerás " para lograr la resolución de un algoritmo complejo lo más recomendable es dividir ese problema en pequeñas partes de manera que se vuelva sencillo y fácil de implementar pero para eso se debe de hacer un análisi del algoritmo ya que no siempre será necesario implementar la recursividad

Bibliografía

Figura a la derecha: recursividad

http://es.wikipedia.org/wiki/Algoritmo_divide_y_vencer%C3%A1s">
http://www.ldc.usb.ve/~gabro/teaching/CI2126/OrdenamientoRecursion.htm