Recursividad (2016)

Apunte Español
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Ingeniería Informática - 2º curso
Asignatura Laboratori de Programació
Año del apunte 2016
Páginas 2
Fecha de subida 27/06/2017
Descargas 0
Subido por

Vista previa del texto

RECURSIVIDAD PARADIGMA DIVIDE Y VENCERÁS 1) Divide el problema en otros idénticos, pero más pequeños => sub-problemas.
2) Solucionar los sub-problemas recursivamente.
3) Combinar las soluciones de los sub-problemas.
Ejemplo: Búsqueda binaria: buscar un elemento en un array ordenado.
o Dividir => comprobar el elemento del medio.
o Solucionar => búsqueda recursiva en 1 sub-array.
o Combinar => trivial Recurrencia: T(n) = 1 x T(n / 2) + O(1) Complejidad: O(log n) ¿QUÉ ES LA RECURSIVIDAD? La programación recursiva es una alternativa diferente para implementar estructuras de repetición. Es parte fundamental de la estrategia de resolución de problemas “divide y vencerás”.
Implementación de una rutina recursiva Implementar una rutina recursiva consiste en encontrar el caso base y caso general del problema a implementar.
1) Si se cumple el caso base => generamos el resultado para este caso.
2) Si no se cumple (caso general) => generamos el resultado de la solución recursiva descomponiendo el problema a un problema de complejidad n – 1.
Ejemplo: def factorial(n): #Caso Base if n == 0 or n == 1: return 1 else: #Caso general return n * factorial(n-1) ORDENAR ELEMENTOS DE UNA SECUENCIA Ejemplo: MergeSort: ordena los elementos de una lista o Dividir => divide la secuencia en dos (por la mitad). Se ordenan las dos mitades con el algoritmo mergeSort de forma recursiva.
o Vencer => se considera que una secuencia de un elemento está ordenada o Combinar => se unen las dos mitades ya ordenadas hasta recuperar la secuencia original completamente ordenada.
Dividir la secuencia por la mitad => O(1) Complejidad: O(n · log n) RECURSIVIDAD EN LISTAS ENCADENADAS - Caso base => lista vacía.
Caso general => se aplica la operación recursiva sobre el resto de la lista: h.next ¿Cuál es la lista más pequeña sobre la que se puede contar? - Una lista vacía, nº elementos = 0.
¿Cómo obtener la cantidad de elementos que tiene una lista si se sabe cuántos elementos tiene el resto de la lista? - 1 + cantidad de elementos del resto de la lista.
Implementación: def listCount(self, t): if(t == None): return 0 return(1 + self.listCount(t.getNext())) ...