Recursividad

* Los problemas pueden ser redefinidos en términos de uno o más subproblemas, idénticos en naturaleza al problema original pero menores en tamaño.

*  Uno o más subproblemas tienen solución directa o conocida, no recursiva.

*  El problema se reduce sucesivamente a los subproblemas de soluciones conocidas.

*  La solución global se construye mediante la solución a los problemas más simples.

Función recursiva F:
   

-          De forma directa: si contiene una llamada explícita a sí misma.

-          De forma indirecta: si llama a otra función Q que, a su vez, contiene una llamada a F.
   

Partes de la función recursiva:
   

-          Llamada recursiva: expresa el problema en términos de otro más pequeño.

-          Caso base: valor (o valores) para el cual se conoce una solución no recursiva.
   

Tipos de recursividad:
   

-          Lineal: sólo hay una llamada recursiva.

-          No lineal: hay más de una llamada recursiva.
   

PILA DEL ORDENADOR

   
Al ejecutar un programa la memoria queda dividida en 2 partes: la zona con el código del programa y la zona donde se guardan los datos (PILA o STACK).
   

è Registro de activación o entorno E: se crea en la Pila (asociado al módulo M) cuando un programa principal llama a una rutina M.

Profundidad de recursión de un módulo recursivo: número de entornos que están presentes en la Pila en un momento dado.
   

Eficiencia de los algoritmos recursivos:
   

-          Tiempo asociado con la llamada a las rutinas: en cada llamada se aloja en la pila un nuevo entorno, con el consiguiente tiempo adicional consumido en esta operación.

-          Ineficiencia inherente: gran cantidad de procesamiento duplicado.