Recursividad

RECURSIVIDAD

Muchas de las estructuras de datos tienen una definición recursiva y por tanto, la recursividad es una buena opción para implementar algunas de sus operaciones.
La recursividad sepuede aplicar tanto en estructuras lineales, cómo en estructuras jerárquicas, principalmente en operaciones que implican búsquedas o recorridos. Se dice que un objeto es recursivo cuando se defineen función de sí mismo. El concepto de recursividad se utiliza con mucha frecuencia en el campo de las matemáticas, ejemplos:

· Los números naturales se definen de la siguiente forma:
- Esnúmero natural.
- y el siguiente de un número natural es también un número natural.
Está definición es recursiva, ya que para definir lo que es número natural estamos usando, de hecho, el concepto denúmero natural.

· La función n! para calcular el factorial de un número natural n cualquiera se define normalmente cómo:
n != { 1 si n=0, n x (n-1)! si n>0

· La suma de dos númerosnaturales también se puede definir de forma recursiva, disponemos de alguna forma de saber cúal es el siguiente y también el predecesor de un natural n. En estas condiciones, la suma de dos naturales, a yb, se puede definir recursivamente:

Suma (a,b) { a si=0, Suma(a,b-1)+1 si b>0


Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en supropia 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 serdividido 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 lasllamadas más pequeñas y suponer que estas quedan resueltas.

BIBLIOGRAFÍA: Manual de algorítmica: recursividad, complejidad, y diseño de algoritmos, Escrito por Jesús Bisbal Riera, Editorial...