Esstructura De Datos

2.1. Definición, características, ventajas y desventajas.

Definición:

La recursividad es una técnica de programación que se utiliza para realizar una llamada a una

función desde ella misma, un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

En programación es mucho más difícil desarrollar una solución recursiva en un lenguaje determinado para resolver un problema específico cuando no se tiene un algoritmo. No es solo el programa sino las definiciones originales y los algoritmos los que deben desarrollarse. En general, cuando encaramos la tarea de escribir un programa para resolver un problema no hay razón para buscar una solución recursiva. La mayoría de los problemas pueden resolverse de una manera directa usando métodos no recursivos. Sin embargo, otros pueden resolverse de una manera más lógica y elegante mediante la recursión.

Características:

-Un subprograma/algoritmo se llama a si mismo para la solución de un problema dentro de un programa.

-El método debe estar definido en función de sí mismo.

-Debe tener una forma de salir y no llamarse infinitamente (caso base).

-No debe generar una secuencia infinita de llamadas así mismo, dicho de otro modo ha de existir al menos un caso base.

- Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos.

-Debe existir una "salida" de la secuencia de llamadas recursivas.

-Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).

Ventajas

-Simplicidad de comprensión

-Solución a problemas recurrentes.

- Son programas cortos.

Desventajas

- Creación de muchas variables

- Puede necesitar mucha memoria -Consume más recursos del sistema, puede volverse lenta la solución.

Debe utilizarse cuando la definición del problema o su solución es inherentemente recursiva, y su equivalente iterativa es compleja.

No debe utilizarse cuando existen soluciones iterativas sencillas.

Tipos de recursividad.

-Recursividad Directa: Consiste en que un método se llama a si mismo desde uno (recursividad simple) ó varios puntos del código (recursividad múltiple).

-Recursividad Indirecta: Consiste en que dos métodos se llaman entre si, es decir, mutuamente.

Ejemplos:

-Recursividad Directa:

//Metodo que suma los dígitos de un entero.

static int sumar_dig(int n)

{

if (n == 0) //caso base

return n;

else

return sumar_dig(n / 10) + (n % 10);

}

static void Main(string[] args)

{

Console.WriteLine(sumar_dig(123));

Console.ReadKey();

}

-Recursividad Indirecta:

//Metodos que determinan si un numero es par o impar,

public bool Par(int n)

{

if (n == 0) return true;

else return Impar(n-1);

}

public bool Impar(int n)

{

if (n == 0) return false;

else return Par(n-1);

...