Ni Mergas

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Tema 3. Recursividad.
Diseño de Algoritmos.
E.U. Politécnica Departamento Lenguajes y Ciencias de la Computación. Universidad de Málaga José Luis Leiva Olivencia. Despacho: I-326D (Edificio E.U.P)/ 3.2.41 (Teatinos-E.T.S.I.I.)

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial(Electricidad)

Introducción
• Definición de Recursividad: Técnica de programación muy potente que puede ser usada en lugar de la iteración, consistente en la invocación de un algoritmo a sí mismo. • Ambito de Aplicación:
– General. – Problemas cuya solución se puede hallar solucionando el mismo problema pero con un caso de menor tamaño.

• Razones de uso:
– Problemas más fáciles de resolver que conestructuras iterativas. – Soluciones elegantes. – Soluciones más simples.

• Condición necesaria: ASIGNACIÓN DINÁMICA DE MEMORIA
Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Introducción
• ¿En qué consiste la recursividad?
– En el cuerpo de sentencias del subalgoritmo se invocaal propio subalgoritmo para resolver “una versión más pequeña” del problema original.

• Aspecto de un subalgoritmo recursivo.
tipo Recursivo(...); { ... Recursivo(...); ... }
Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Introducción
• Ejemplo: Factorial de un natural. 1 si n=0Factorial(n)= n*Factorial(n-1) si n>0 int Factorial(int n) { if (n==0) return 1; else return (n*Factorial(n-1)); }

Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Introducción
• El método de definición de una función en términos de sí misma se llama en matemáticas a una definicióninductiva y conduce naturalmente a una implementación recursiva. • El caso base de 0!=1 es esencial dado que se detiene, potencialmente, una cadena de llamadas recursivas (Caso Base o condición de salida)
Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Introducción
• Tipos derecursividad:
– Si una función o procedimiento se invoca a sí misma, el proceso se denomina recursión directa; si una función o procedimiento puede invocar a una segunda función o procedimiento que a su vez invoca a la primera este proceso se conoce como recursión indirecta o mutua.

Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos.E.U.Politécnica. I.T.Industrial (Electricidad)

Introducción
24
F(4)=4 * F(3)

6 2 1

F(3)=3 * F(2) F(2)=2 * F(1)

F(1)=1 * F(0)
Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Introducción
Registro de Activación. bloque de memoria que contiene la información sobre las constantes yvariables declaradas en el procedimiento, junto con una dirección de retorno, dirección en memoria de la sentencia que causó la llamada al subalgoritmo. Dirección de Retorno. Pila (Stack) Forma especial de organizar la memoria, en la que la información siempre se añade y se suprime por una posición llamada cima . Vinculación(dirección memoria variable). Elementos de Programación I

Departamentode Lenguajes y Ciencias de la Computación

Asignación estática y dinámica de memoria
• Partimos del siguiente ejemplo void uno (int x,int y) { int z; ... ... }

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)

Departamento de Lenguajes y Ciencias de la Computación

Elementos de Programación I

Diseño de Algoritmos. E.U.Politécnica. I.T.Industrial (Electricidad)...