INTRODUCCIÓN

• Definición de Recursividad:
Técnica de programación que puede ser usada de forma alternativa a la iteración. Es posible aplicarla cuando un problema puede ser dividido en problemas más pequeños con el mismo formato que el problema original, y cuando ese desmenuzamiento en problemas más pequeños conduce a un caso sencillo del cual se conoce la solución. Entonces, la técnica recorre el camino inverso para reconstruir la solución del problema original.

• Ambito de Aplicación:
– General
– Problemas cuya solución se puede hallar solucionando el mismo problema en casos de menor tamaño.

• Razones de uso:
– Problemas "casi" irresolubles con las estructuras iterativas.
– Soluciones elegantes.
– Soluciones más simples.

• Condición necesaria : Asignación dinámica de memoria.

• ¿En qué consiste la recursividad?

IDEAS GENERALES
La recursividad es una técnica de resolución de problemas que consiste en reducir un problema complejo en subproblemas, los cuales se guardan en el mismo formato que el original pero, cuya repetida división nos lleva hasta casos sencillos explícitamente resueltos. La posterior recomposición de todos estos subprogramas nos permita reconstruir la solución al problema inicial. Destacamos aquí la importancia que tiene en el proceso la seguridad de poder llegar a casos sencillos cuya solución se conoce. Se llama "condición de corte". Si esta condición no se alcanzase para algún caso, el algoritmo puede caer en un bucle infinito y, por tanto, no resolver el problema.

Un programa recursivo es aquel que cumple dos condiciones:
1) Se llama a sí mismo.
2) Tiene una o varias condiciones de corte que alcanzan de forma segura cuando se aplica la recursión a todos los problemas iniciales admisibles.

La recursividad tiene la ventaja de que problemas complicados se implementan bajo una forma escueta y compacta cuando su solución se plantea según la estrategia recursiva:
– En el cuerpo de sentencias del subalgoritmo se invoca al propio subalgoritmo para resolver "una versión más pequeña" del problema original.
– Habrá un caso (o varios) tan simple que pueda resolverse directamente sin necesidad de hacer otra llamada recursiva.

• Aspecto de un subalgoritmo recursivo:

ALGORITMO Recursivo(...)
INICIO
...
Recursivo(...);
...
FIN


Ejemplo: Factorial de un natural.

1 si n == 0
Factorial(n)= n*Factorial(n-1) si n > 0

Ejemplo: Factorial de un natural n.
ALGORITMO Factorial(n)
VAR fact
INICIO
SI n == 0 ENTONCES fact = 1
SINO fact = n*Factorial(n-1)
FINSI
DEVOLVER fact
FIN


Volver al índice
Siguiente