Recursividad en programación

Recursividad

• Una definición es recursiva si el objeto o concepto definido aparece en la definición misma.

Aplicaciones de la Recursividad

• Generación y procesamiento de imágenes y gráficos fractales, compuestos por versiones más simples de la figura original.
• Recorrido y procesamiento de estructuras de datos no lineales como árboles y grafos.

Condiciones para la Recursividad

• Una función debe tener al menos una invocación a sí misma.
• Antes de invocarse, debe tener condiciones de control para interrumpir el proceso recursivo al alcanzar situaciones triviales.
• Una definición recursiva correcta evita la recursión infinita asegurando elementos para cerrarla lógicamente.

Definición Recursiva de Bosque

• Un bosque es un conjunto de árboles que puede estar vacío, o contener uno o más árboles agrupados con otro bosque.

Análisis de Bloque de Código Recursivo

• La versión recursiva puede ser más simple, pero utiliza memoria de stack en cada invocación.
• La versión iterativa puede ser más conveniente.

Gráficos Fractales

• Un fractal es una figura compuesta por versiones más simples y pequeñas de la figura original.

Coordenadas de Pantalla

• El origen se encuentra en la esquina superior izquierda de la pantalla o ventana.
• Las filas con número de orden más bajo están más cerca del borde superior.

Función Ackermann

• Es una función recursiva con dos argumentos enteros no negativos.

Stack Segment

• Cuando se invoca una función, se asigna un bloque de memoria en el Stack Segment.
• Dentro de este bloque, la función crea parámetros, variables locales y comienza la ejecución.
• El segmento funciona como una pila LIFO: el último dato en llegar es el primero en salir.
• Se utiliza como soporte interno en la invocación de funciones, llenándose con cada invocación y vaciándose al regresar.
• Cada instancia recursiva almacena la dirección de retorno y las variables locales en el Stack Segment.
• A medida que se desarrolla la recursión, el Stack Segment se llena, y se vacía cuando una instancia finaliza.

Factorial

• Si n = 0, entonces 0! = 1.
• Si n > 0, entonces n! = n * (n-1)!.

Potencia

• Si n==0 entonces es igual a 1
• a * potencia(a, n-1) si n>0

Producto

• si a == 0 or b == 0 entonces es igual a 0
• a + producto (a, b-1) si a > 0 y b > 0

Fibonacci

• Versión iterativa: tiempo proporcional a n (lineal).
• Versión recursiva: tiempo proporcional a bn (exponencial, para algún b > 1), con un orden de 1.8n.

Algoritmos de Ordenamiento

• Los algoritmos de ordenamiento simples funcionan bien con arreglos pequeños, pero tienen mal rendimiento con arreglos grandes.

Intercambio Directo (Burbuja/Bubblesort)

• Se comparan elementos adyacentes en pasadas sucesivas, llevando los mayores al final del arreglo.
• Una bandera de corte termina el proceso si no hay intercambios en una pasada.

Selección Directa

• En cada pasada, se determina el menor elemento y se lleva a la casilla pivot.

Inserción Directa

• Se asume un subconjunto inicial ordenado y se agregan elementos al grupo ordenado en pasadas sucesivas.

Shellsort

• Mejora la inserción directa armando subconjuntos ordenados con elementos a distancia h > 1, terminando con h = 1.
• Con h = 1, se convierte en inserción simple, garantizando el orden final.
• El tiempo de ejecución para el peor caso es O(n1.5).
• Al usar una serie de incrementos decrecientes, los subconjuntos contendrán elementos similares, sin asegurar una buena organización antes de la última pasada.

Heapsort

• Encuentra sucesivamente el menor o mayor elemento para llevarlo a su posición final de forma veloz.
• Es eficiente tanto en el caso promedio como en el peor caso.
• Arma el heap en el mismo vector sin usar memoria extra.

Análisis de Algoritmos

• Es la rama de la computación que mide la eficiencia de un algoritmo.
• Los factores que influyen en la eficiencia son tiempo de ejecución, consumo de memoria, y complejidad del código.

Diferencia entre el Peor Caso y el Caso Promedio

• El peor caso describe la configuración de datos de entrada más desfavorable.
• El caso promedio describe una configuración aleatoria de datos.

Notación Big O

• Muestra una cota superior para el tiempo de ejecución, expresando el rendimiento de un algoritmo.
• O(1): Tiempo de ejecución constante, sin importar el volumen de datos.
• O(log(n)): Logarítmico, dividiendo un lote de datos en dos sucesivamente.
• O(n): Lineal, procesando cada dato una vez.
• O(nlog(n)): Dividiendo y procesando particiones de datos sin desechar ninguna.
• O(n2): Cuadrático, combinando dos ciclos de n vueltas cada uno.
• O(n3): Cúbico, combinando tres ciclos de n repeticiones cada uno.
• O(2n): Exponencial, explorando combinaciones de soluciones exponencialmente crecientes.

Formas de Crecimiento de las Funciones

• O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n2) < O(n3) < O(2n)

Formalización de la Notación Big O

• Una función polinómica de grado k es de orden nk.
• logb(n) = O(log(n))

Conteo Exhaustivo, Análisis Asintótico, Orden de Complejidad

• El conteo exhaustivo determina una expresión rigurosa de operaciones críticas.
• El análisis asintótico determina el comportamiento general para valores grandes del tamaño del problema.
• El orden de complejidad "O(g(n))" es un conjunto de funciones que se comportan asintóticamente de la misma forma.

Comportamiento Asintótico de los Algoritmos de Ordenamiento

• Burbuja: O(n2) (peor caso), O(n) (mejor caso).
• Selección directa: O(n2) (peor caso).
• Inserción directa: O(n2) (peor caso).
• Quicksort: O(nlog(n)) (caso medio), O(n2) (peor caso).
• Heapsort: O(nlog(n)) (caso medio).
• Shellsort: O(n1.5).

Otras Notaciones Típicas

• O (Big O): Cota superior para el tiempo de ejecución.
• Ω (Omega): Tiempo de ejecución o espacio de memoria ocupado.
• Θ (Theta): Una función f se comporta de forma similar a múltiplos de otra función g.
• o (o minúscula o little): Similar a O(), pero considerando solo relaciones de menor estricto.

Notación Big O en Algoritmos de Ordenamiento

• La notación Big O rescata el término más significativo en la expresión, descartando constantes que podrían no coincidir entre algoritmos.

Características del Algoritmo Shellsort

• El algoritmo Shellsort es difícil de analizar para determinar su rendimiento en forma matemática.
• Una implementación es una mejora del algoritmo de Inserción Directa, organizando subconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, terminando con h = 1.

Estructuras de Datos Lineales: Pilas y Colas

Estructuras

• Nativas las que vienen con el lenguaje
• Abstractas: no vienen con el lenguaje

Tipo de Estructura

• Lineal (Pilas y Colas): si cada elemento de esta tiene un único elemento sucesor inmediato (o ninguno si es el último) y también tiene un único elemento antecesor inmediato (o ninguno si es el primero).
• No Lineales (Árboles y Grafos): si sus elementos pudiesen tener más de un sucesor o antecesor inmediato.

Abstracción

• Abstracción de Datos: busca captar el conjunto de datos más relevante para representar un tipo abstracto.
• Abstracción Funcional: buscar identificar el conjunto de procesos relevante para esos datos.

Pilas (Stacks)

• Estructura lineal donde los elementos se apilan, siendo el último en entrar el primero en salir (LIFO).
• Ejemplo: procesar datos en orden inverso a su entrada.

Colas (Queues)

• Estructura lineal donde los elementos se organizan uno detrás del otro, quedando uno al principio, y otro al final.
• El primer elemento en entrar es el primero en salir (FIFO).
• Ejemplo: Procesar una secuencia de datos en el mismo orden en el que ingresaron.

Estructuras No Lineales: Árboles Binarios de Búsqueda

• Un árbol binario es una estructura de datos no lineal que puede estar vacía o contener un nodo raíz.
• Si un nodo raíz existe, tendrá dos elementos, con estas características:
• Cada sub-conjunto tiene intersección vacía
• Los subconjuntos son a su vez árboles binarios, y se designan respectivamente como subárbol izquierdo y subárbol derecho.

Términos Principales en Árboles Binarios

Enlaces/Arcos

• Referencias, punteros o índices de un arreglo.

Nodo

• Dado un nodo x:
• Los dos nodos siguientes a x se llaman hijos de x.
• El nodo del cual depende x hacia arriba, se dice el padre de x.

Nivel

• Número de arcos desde la raíz.

Altura

• Nivel máximo del árbol.

Búsqueda

• Se realiza una comparación por nivel.
• En el peor de casos es O(log(n)) si la altura del árbol es O(log(n)).
• Si es una diagonal de altura n, el tiempo de ejecución es O(n).

Recorrido de Árboles Binarios

Pila

• Para almacenar en orden LIFO las direcciones de los nodos visitados.

Preorden

• Cada nodo se visita al llegar por primera vez.
  • Visitar el nodo raíz.
  • Recorrer en Preorden el subárbol izquierdo.
  • Recorrer en Preorden el subárbol derecho.

Entreorden

• Cada nodo se visita al volverlo desde la izquierda.
  • Recorrer en Entreorden el subárbol izquierdo.
  • Visitar el nodo raíz.
  • Recorrer en Entreorden el subárbol derecho.

Postorden

• Cada nodo se visita al volverlo desde la derecha.
  • Recorrer en Postorden el subárbol izquierdo.
  • Recorrer en Postorden el subárbol derecho.
  • Visitar el nodo raíz.

Construcción de Árboles

• Para construir un árbol, se necesitan conocer:
• Recorrido Preorden y Entreorden.
• Recorrido Postorden y Entreorden.

Condiciones en el Recorrido Preorden

• El recorrido será en secuencia ordenada si el árbol es una diagonal con todos los hijos izquierdos nulos.

Árbol Desbalanceado

• El tiempo de búsqueda en el peor de los casos es O(n).

Árbol Balanceado

• Su altura es la mínima posible para la cantidad de nodos.

Estructuras No Lineales: Grafos

• Un Grafo está compuesto por n nodos y m arcos donde un arco une dos vértices.

Componentes de un Grafo

• Vértices: A, B, C, D, E, F, G, H
• Arcos: (A, B), (A, D), (A, C), (E, E), (D, E), (E, A), (F, G)

Características de los Grafos

• Un grafo puede tener subgrafos no unidos entre sí por arcos que los conecten, o nodos aislados (sin arcos incidentes).
• No es obligatorio que un vértice sea punto de partida o de llegada de algún arco; puede estar aislado.
• Dos nodos pueden tener varios caminos de distinta longitud, se dicen adyacentes si existe un arco que los une.
• Si existe un camino de cualquier longitud desde un vértice que lleve de retorno al mismo vértice, entonces el grafo tiene un ciclo, y se denomina grafo cíclico.

Grado de un Nodo

• Cantidad de arcos incidentes al nodo (arcos que tienen al nodo como partida o como llegada).
• Entre Grado: cantidad de nodos que coinciden en el nodo de llegada
• Fuera de grado: cantidad de nodos que coinciden en el nodo de partida.

Tipos de Grafos

Grafo Dirigido

• Los arcos indican relaciones entre nodos, y el sentido de cada arco indica el nodo de partida y de llegada.

Grafo No Dirigido

• El arco que conecta dos vértices puede recorrerse indistintamente.

Grafo Ponderado

• Cada arco tiene asociado un valor, peso o ponderación.

Implementación Matricial de Grafos

Grafo Dirigido

• Las filas representan los vértices de partida y las columnas los de llegada.

Grafo no dirigido

• Simétrico: ambos arcos existen (A, B) y (B, A).
• Reflexivo: todo vértice se relaciona consigo mismo.
• Transitivo: si existen (x, y) e (y, z) entonces existe (x, z)..

Grafo Ponderado

• Cada casilla apunta a un objeto que representa un arco, almacenando los atributos necesarios.
• No es viable almacenar solo un entero por cada casillero o si se almacena directamente el pedo del arco, un problema posible es el de la ambigüedad del cero, ya que no es posible distinguir si el cero es el peso de un arco o que el indicador de que no exista el arco

Algoritmo de Quicksort

Creador

• Charles Antony Richard Hoare.

Características

• Quicksort acelera el cambio de posición de elementos menores y mayores, mejorando el algoritmo Bubblesort.
• Quicksort requiere una función de comparación para determinar el orden de los elementos.

Caso Promedio

• La altura del árbol de invocaciones recursivas es log(n).
• El tiempo de ejecución es O(nlog(n)).

Peor Caso

• La altura del árbol de invocaciones recursivas es n.
• El tiempo de ejecución es O(n2).
• Ocurre cuando el arreglo de entrada tiene elementos que hacen que el pivot sea siempre el menor o el mayor de la partición.

Recomendación

• Obtener el pivot por la mediana de tres para evitar el peor caso.

Pivot en Quicksort

• Elegir el primer elemento como pivot es mala idea porque aumenta el riesgo de caer en el peor caso si el arreglo esta ya ordenados o casi ordenados.

Calcular Mediana entre el primero, el central y el último elemento de una partición.

Esquema Esencial de un Algoritmo Divide y Vencerás

• Cada elemento se expresa en notación O(1).

Estrategias de Resolución de Problemas

• Técnicas para encontrar la solución a un problema.

Fuerza Bruta

• Aplica ideas intuitivas y directas, produciendo algoritmos de mal rendimiento.
• El problema del Viajante es 𝑂(𝑛!), ordenamiento por Selección Directa.

Recursión

• Un proceso se invoca a sí mismo.
• Útil en generación de imágenes y gráficos fractales.
• Recorrido y procesamiento de estructuras de datos no lineales como árboles y grafos.

Backtracking (Vuelta Atrás)

• Base recursiva que implementa soluciones de prueba y error.
• Más eficiente que la Fuerza Bruta, eliminando caminos incorrectos.
• Problema de las Ocho Reinas y juegos de optimización combinatoria.

Algoritmos Ávidos o Devoradores (Greedy Algorithms)

• Aplica una regla intuitivamente válida en cada paso.
• Problema del árbol de expansión mínimo de un grafo y algoritmo de Dijkstra.
• Problema del cambio de monedas requiriendo la moneda de 1 centavo.

Divide y Vencerás

• El conjunto de datos se divide en subconjuntos del mismo tamaño y se aplica recursión.
• Quicksort y Mergesort para ordenamiento de arreglos.

Programación Dinámica

• Calcula y almacena los resultados de subproblemas para re-usarlos en el cálculo del problema mayor.
• útl en problemas de alineación de secuencias.

Problema de las Ocho Reinas: Diagonales

• Diagonales normales e inversas.
• La suma es constante en diagonales inversas entre el número de columna y el número de fila.
• La cantidad total de diagonales de la matriz es 30.

Estructuras para representar las Reinas

qr (queens in row)

• Con 8 casilleros
• qr[fil] = True indicará que la fila fil está libre de reinas

qid (de queens on inverse diagonal)

• Con 15 casilleros
• qid(de queens on inverse) = True indicará que la diagonal inversa di está libre de reinas.

qnd (de queens on normal diagonal)

• Con 15 casilleros
• qnd(of queens on normal diagonal)= True indicará que la diagonal normal dn está libre de reinas

Diagonales Normales

• El resto de los elementos en la diagonal es constante = [-7..7].
• Se representan con un arreglo qnd de 15 elementos
• qnd [(column - row) + 7(

Diagonales Inversas

• La suma de los elementos siempre es constante.
• Entre los intervalos [0..14].
• qnd [(column - row) + 14(

Soluciones Incorrectas:

• Cuando NO tienen que enfrentarse la Reinas.