Estructura De Datos

Índice:

Tema: Pagina:

Definición de Recursividad……………………………………………….1

Procedimientos Recursivos……………………………………………….2

Ejemplos de casos Recursivos……………………………………………3

Conclusiones Personales Del Tema……………………………………...6

Bibliografía / linkografia…………………………………………………….6

Definición Recursividad.

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función.

Las funciones del C++ pueden ser recursivas, es decir, se pueden llamar a sí mismas. Lo único interesante de las funciones recursivas es que las variables declaradas dentro del cuerpo de la función que sean estáticas (static) no pierden su valor entre llamadas, es decir, no se crean y se destruyen en la pila, sino que ocupan siempre la misma posición, y por tanto cada modificación que se haga de la variable será válida entre sucesivas llamadas.

Otra ventaja de esta aproximación es que no importa para la recursividad que la variable mantenga su valor después de una llamada recursiva (por ejemplo una variable temporal para intercambios), al declararla estática no tenemos que reservar espacio para ella en cada llamada (las llamadas recursivas consumen menos pila).

Aunque comento esto para funciones recursivas, la verdad es que esto se cumple para todas las funciones, luego podemos tener una variable estática que se use para contar el número de veces que se llama a una función ().

Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. 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.

Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos más simples no recursivos.

Procedimientos Recursivos.

Los procesos recursivos o (funciones recursivas) son llamados desde otro proceso. Un proceso puede ser recursivo tanto de forma directa (si es llamada a sí misma) o de forma indirecta (si llama a una función que luego la llama).

Existen algunos problemas que pueden ser resueltos de forma más eficiente (o su resolución puede ser más naturalmente pensada) utilizando procesos recursivos.

Un proceso puede dar origen a un típico problema en programación, llamado recursión infinita, que es cuando un proceso se llama a sí mismo infinitas veces. Esto detiene el normal funcionamiento de un programa.

Para que esto no suceda un proceso recursivo debe ser muy bien pensado. Principalmente un proceso recursivo debe saber resolver el caso más simple, llamado caso base. Si el proceso es llamado con el caso base, inmediatamente retorna el resultado (no necesita volver a llamarse a sí mismo para poder resolverlo).

Si el proceso es llamado con un caso más complejo, los sucesivos llamados a sí mismos irán virtualmente descomponiendo ese caso hasta llegar a un caso base, para luego determinar el resultado final del proceso.

Ejemplos de Casos Recursivos.

Un ejemplo de programa recursivo en C, el factorial:

int factorial(int n)

{

if (n == 0) return 1;

return n * factorial(n-1);

}

Como se observa, en cada llamada recursiva se reduce

...