Parcial 5 Teórico Todo (AED Ciclo 2024) PDF

Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Ficha 14 Recursividad 1.] Introducción. Cuando en la práctica se habla de recursividad, se está haciendo referencia a una muy...

Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Ficha 14 Recursividad 1.] Introducción. Cuando en la práctica se habla de recursividad, se está haciendo referencia a una muy particular forma de expresar la definición de un objeto o un concepto. Esencialmente, una definición se dice recursiva si el objeto o concepto que está siendo definido aparece a su vez en la propia definición. Consideremos por ejemplo, la siguiente definición: Una frase es un conjunto de palabras que puede estar vacío, o bien puede contener una palabra seguida a su vez de otra frase. Estamos frente a una definición recursiva, puesto que el objeto definido (la frase) se está usando en la misma definición, al indicar que una frase puede ser una palabra seguida a su vez de otra frase. Al plantear una definición recursiva debe tenerse cuidado con los siguientes elementos : 1. Una definición recursiva correctamente planteada, exige que la definición agregue conocimiento respecto del concepto u objeto que se define. No basta con que el objeto definido aparezca en la definición, pues si sólo nos limitamos a esa regla podrían producirse definiciones obviamente verdaderas, pero sin aportar conocimiento alguno. Por ejemplo, si decimos que: Una frase es una frase. no cabe duda en cuanto a que esa afirmación es recursiva, pero de ninguna manera estamos definiendo lo que es una frase. En todo caso, lo que tenemos es una identidad, y no una definición. En cambio en la definición original que dimos de la idea de frase, encontramos elementos que nos permiten construir paso a paso el concepto de frase, a partir de la noción de frase vacía y la noción de palabra, y esos elementos son los que agregan conocimiento al concepto. 2. Por otra parte, una definición recursiva correctamente planteada debe evitar la recursión infinita que se produce cuando en la definición no existen elementos que permitan cerrarla lógicamente. Se cae así en una definición que, aunque agrega conocimiento, no termina nunca de referirse a sí misma. Por ejemplo, si la definición original de frase fuera planteada así: Una frase es un conjunto que consta de una palabra seguida a su vez de una frase. tenemos que esta nueva definición es recursiva y aparentemente está bien planteada, por cuanto agrega conocimiento al indicar que una frase consta de palabras y frases. Pero al no indicar que una frase puede estar vacía, la noción de frase se torna en un concepto sin fin: cada vez que decimos frase, pensamos en una palabra, y en otra frase, lo cual a su vez lleva a otra palabra y a una nueva frase, y así sucesivamente, sin solución de continuidad. Las definiciones recursivas no son muy comunes en la vida cotidiana porque en principio, siempre existe y siempre resulta más simple pensar y entender una definición directa, sin la Ing. Valerio Frittelli - 288 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad vuelta hacia atrás que supone la recursividad. La misma noción de frase, puede definirse sin recursividad de la forma siguiente: Una frase es una sucesión finita de palabras, que puede estar vacía. y esta definición resulta más natural y obvia (incluso podría no indicarse que la frase puede estar vacía, y la definición seguiría teniendo sentido). Sin embargo, en ciertas disciplinas como la Matemática, la recursividad se usa con mucha frecuencia debido a que existen problemas cuya descripción simbólica es más compacta y consistente con recursividad que sin ella. Consideremos el típico y ya conocido caso del factorial de un número n. Como sabemos, si n es un entero positivo o cero, entonces el factorial de n (denotado como n!), se puede definir sin recursividad, como sigue: si n = 0  0! = 1 n! = si n > 0  n! = n * (n-1) * (n-2) * … * 3 * 2 * 1 Es decir: si n es cero, su factorial vale uno. Pero si n es mayor a cero, su factorial es el producto de n por todos los enteros positivos anteriores a n, hasta el uno. De esta forma, el factorial de 4 sería: 4! = 4 * 3 * 2 * 1 4! = 24 La fórmula dada para el cálculo del factorial es sencilla, pero incluye una serie de puntos suspensivos que no siempre son bien recibidos, pues se presupone que quien lee la fórmula será capaz de deducir por sí mismo la forma de llenar el espacio de los puntos suspensivos. Eso podría no ser tan simple si la fórmula fuese más compleja. La recursividad ofrece una alternativa de notación más compacta, evitando los puntos suspensivos. Por ejemplo, si se observa la definición para n > 0, tenemos: n! = n * (n – 1) * (n – 2) *... * 3 * 2 * 1 En esta fórmula es claramente visible que la expresión (n – 1) * (n – 2) *... * 3 * 2 * 1 es equivalente al factorial del número (n – 1): se está multiplicando a (n – 1) por todos los números enteros anteriores a él, hasta llegar al uno. Por lo tanto, la definición original podría escribirse así: n! = n * (n – 1)! En otras palabras: si n > 0, entonces el factorial de n es igual a n multiplicado por el factorial de (n – 1). Si reunimos todo en una definición global, tenemos: si n = 0  0! = 1 n! = si n > 0  n! = n * (n-1)! y llegamos así a una definición recursiva: para definir el factorial de n, en la misma definición se recurre al factorial de (n – 1). Observemos que la condición si n = 0 entonces 0! = 1 Ing. Valerio Frittelli - 289 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad es la que evita la recursión infinita, y que la condición si n > 0 entonces n! = n * (n – 1)! provoca el paso recursivo, pero agregando conocimiento al mismo: un factorial es en última instancia un producto de un número por el factorial del número precedente. 2.] Programación recursiva. La noción de definición recursiva vista hasta aquí sirve como punto de partida para plantear algoritmos en forma recursiva (de hecho, la definición recursiva del factorial que se estudió, no es más que un algoritmo recursivo para calcular ese factorial). Prácticamente todos los lenguajes de programación modernos soportan la recursividad, a través del planteo de subrutinas recursivas. En Python, la idea es que un algoritmo recursivo puede implementarse a través de funciones de comportamiento recursivo. En términos muy básicos, una función recursiva es una función que incluye en su bloque de acciones una o más invocaciones a sí misma. En otras palabras, una función recursiva es aquella que se invoca a sí misma una o más veces. En esencia, entonces, la siguiente función es recursiva (aunque aclaramos que está mal planteada): def procesar(): procesar() Si la condición para ser recursiva es invocarse a sí misma, entonces la función anterior cumple el requisito: de hecho, lo único que hace es invocarse a sí misma. Sin embargo, como ya se dijo, está mal planteada: aún sin saber mucho respecto de cómo trabaja la recursividad en Python, un breve análisis inmediatamente permite deducir que una vez invocada esta función provoca una cascada infinita de auto-invocaciones, sin realizar ninguna tarea útil. Como ya veremos, este proceso recursivo infinito provocará tarde o temprano una falla de ejecución por falta de memoria, y el programa se interrumpirá. ¿Por qué está mal planteada esta función? En realidad ya conocemos la respuesta: cuando se introdujo a nivel teórico el tema de las definiciones recursivas bien planteadas en la sección anterior, se indicó que estas deberían agregar conocimiento respecto del concepto definido, y evitar la recursión infinita incluyendo una condición que corte el proceso recursivo. Y bien: la función procesar() aquí planteada no incluye ninguno de los dos elementos. por lo que no corresponde a una definición recursiva bien planteada. Para poner un ejemplo conocido, supongamos que se desea plantear una función recursiva para calcular el factorial de un número n que entra como parámetro. Si planteáramos una función factorial(n) para calcular recursivamente el factorial de n, pero lo hiciéramos a la manera incorrecta que vimos antes para procesar(), quedaría: def factorial(n): return factorial(n) La función factorial así planteada, correspondería a "definir" el factorial así: El factorial de n es igual al factorial de n. Ing. Valerio Frittelli - 290 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Y como se ve, ni la definición ni la función agregan conocimiento al concepto y son por lo tanto, incorrectas. Un segundo intento, sería: def factorial(n): return n * factorial(n - 1) En este caso, la función mostrada correspondería a definir al factorial de la siguiente forma: n! = n * (n – 1)! lo cual agrega conocimiento pero cae en recursión infinita, pues la invocación factorial(n–1) provoca una nueva llamada, y esta a su vez otra, y así en forma continua, sin definir en qué momento detener el proceso. La recursión infinita se evita considerando que si n == 0, entonces el factorial de n es 1. Una simple condición en la función y queda la versión final, ahora correcta: def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) 3.] Seguimiento de la recursividad. En el punto anterior vimos que una función recursiva bien planteada debe contener una condición de corte para evitar la recursión infinita, e incluir una o mas invocaciones a sí misma pero agregando algún tipo de explicitación del proceso. Ahora bien... ¿Cómo funciona todo esto? ¿Cómo hace un lenguaje de programación para ejecutar una función recursiva? Una persona poco entrenada en programación recursiva podría creer que la función factorial() que planteamos antes está incompleta (porque no incluye ningún ciclo para calcular el factorial), o asumir que es correcta pero no comprender nada en absoluto respecto de su funcionamiento. Para entender como trabaja una función recursiva, lo mejor es intentar un seguimiento a partir de un esquema gráfico. Supongamos que se invoca a la función factorial() para calcular el factorial del número 4. O sea, supongamos la siguiente invocación: y = factorial(4) Cuando una función es invocada (sea o no recursiva) automáticamente se asigna para ella un bloque de memoria en el segmento de memoria conocido como Stack Segment (o Segmento de Pila). Dentro de ese bloque, la función crea y aloja sus parámetros formales y variables locales y luego comienza a ejecutarse. Se dice que se está ejecutando una instancia de la función (y en este caso, es la primera instancia). Recordando que la función factorial() toma como parámetro una variable n, en la siguiente figura representamos con un rectángulo al bloque de memoria asignado a la función en esta primera instancia de ejecución: Ing. Valerio Frittelli - 291 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Figura 1: Primera invocación a la función factorial(). El parámetro queda: n=4 Ejecuta: return 4 * factorial (3) y = factorial(4) Instancia 1 - Ejecutando Stack Segment (Memoria de stack) El valor 4 enviado como parámetro actual, es asignado en el parámetro formal n. Luego, la función verifica si n vale cero. En este caso, la condición sale por falso y ejecuta la rama else, que expresa: return n * factorial(n – 1) Como n vale 4, la expresión se evalúa como return 4 * factorial(3) Ahora bien: en esta última expresión se está invocando nuevamente a la función factorial(), pero ahora para calcular el factorial de 3. Aquí se produjo una llamada recursiva y el lenguaje Python actúa frente a ella de manera sencilla: trata a esa invocación recursiva como trataría a cualquier invocación normal de función: simplemente, le asigna a esa segunda instancia de ejecución una nueva área de memoria de stack, para que a su vez esta segunda instancia aloje en ella sus variables locales y parámetros formales. Nuevamente, mostramos un rectángulo para representar a la segunda instancia: Figura 2: Segunda invocación (recursiva) a la función factorial(). El parámetro queda: n=3 Ejecuta: return 3 * factorial(2) Instancia 2 – Ejecutando El parámetro queda: n=4 Ejecuta: return 4 * factorial(3) y = factorial(4) Instancia 1 – Esperando Stack Segment (Memoria de stack) Lo importante aquí es entender que al asignar memoria para la segunda instancia de ejecución, la función vuelve a crear sus variables locales y parámetros formales, sin interferir con los ya creados para la primera instancia. El área de memoria de stack asignada a la primera instancia sigue ocupada, pero momentáneamente inactiva (la primera instancia de ejecución está esperando a que la segunda finalice). Ing. Valerio Frittelli - 292 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad En otras palabras: la segunda instancia se comporta (y de hecho, es) como una función diferente de la primera, y cada una de ellas tiene sus propias variables. Aún cuando estas variables tienen los mismos nombres o identificadores en ambas instancias de ejecución, son variables diferentes porque ocupan lugares distintos de la memoria. El bloque de memoria de stack de la primera instancia, contiene una variable n cuyo valor es 4, y el bloque de memoria de stack de la segunda instancia contiene otra variable (también llamada n), pero con valor igual a 3. Mientras está activa (o sea, mientras se está ejecutando) la segunda instancia, la variable que se usa es la n cuyo valor es 3. Cuando se ejecuta la segunda instancia, se repite el esquema que ocurrió en la primera, pero ahora con n valiendo 3. La expresión: return 3 * factorial(2) provoca a su vez otra llamada recursiva, que es alojada en otra área de memoria de memoria de stack. Esta tercera instancia de ejecución produce además una nueva creación de variables locales: Figura 3: Tercera invocación (recursiva) a la función factorial(). El parámetro queda: n=2 Ejecuta: return 2 * factorial(1) Instancia 3 – Ejecutando El parámetro queda: n=3 Ejecuta: return 3 * factorial(2) Instancia 2 – Esperando El parámetro queda: n=4 Ejecuta: return 4 * factorial(3) y = factorial(4) Instancia 1 – Esperando Stack Segment (Memoria de stack) La tercera instancia lanza una nueva llamada recursiva y otra asignación de memoria de stack para la cuarta instancia, al hacer: return 2 * factorial(1) Y la cuarta instancia a su vez lanza una quinta instancia haciendo: return 1 * factorial(0) con lo que nuestro esquema de memoria de stack queda así: Ing. Valerio Frittelli - 293 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Figura 4: Memoria de stack luego de cinco invocaciones recursivas a la función factorial(). El parámetro queda: n=0 Ejecuta: return 1 Instancia 5 – Ejecutando El parámetro queda: n=1 Ejecuta: return 1 * factorial(0) Instancia 4 – Esperando El parámetro queda: n=2 Ejecuta: return 2 * factorial(1) Instancia 3 – Esperando El parámetro queda: n=3 Ejecuta: return 3 * factorial(2) Instancia 2 – Esperando El parámetro queda: n=4 Ejecuta: return 4 * factorial(3) y = factorial(4) Instancia 1 – Esperando Stack Segment (Memoria de stack) Observemos con mucha atención la quinta instancia de ejecución: en ella, el valor de n es cero, y por lo tanto en esta quinta instancia la condición: if n == 0: return 1 es evaluada en verdadero, ejecutando entonces la instrucción return 1. Entiéndase bien: hasta aquí, había en memoria cinco instancias ejecutándose y/o esperando. Si bien se trataba de la misma función invocándose a sí misma varias veces, Python (y todo lenguaje que soporte recursividad) trata a estas instancias como funciones diferentes que piden memoria por separado. Ing. Valerio Frittelli - 294 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Ahora bien: cuando alguna de las funciones de esa cascada recursiva logra finalizar (como pasa con la quinta instancia de nuestro último gráfico), comienza a desarrollarse automáticamente un proceso conocido como proceso de vuelta atrás o backtracking. La cuestión es simple, aunque un poco extensa de explicar: la función que logra finalizar libera su área de memoria de stack y retorna su valor hacia la instancia de ejecución que originalmente la había llamado. En nuestro caso, la instancia 5 retorna el valor 1 (que es el valor del factorial de 0) hacia la instancia 4 (que es la que había pedido el factorial de 0). En la instancia 4 ahora se conoce entonces cuánto vale el factorial de 0, por lo cual a su vez puede calcular el valor de 1 * factorial(0) que es igual a 1. Cuando la instancia 4 calcula este valor (que es el factorial de 1), la instancia 4 termina de ejecutarse retornando el valor 1 a la instancia 3 (que fue la que pidió el factorial de 1). En la instancia 3 se calcula ahora el factorial de 2, haciendo 2 * factorial(1) cuyo valor es 2. Ese resultado se retorna a la instancia 2, en donde a su vez se calcula 3 * factorial(2) que vale 6. Por fin, el valor 6 es retornado a la instancia 1, donde se calcula el valor 4 * factorial(3) cuyo valor es 24 y es justamente el factorial de 4 que se quería calcular originalmente. Ese resultado es devuelto al punto original de llamada, y la función factorial() termina (¡por fin!) de ejecutarse. Gráficamente, el proceso de vuelta atrás o backtracking completo puede verse en la Figura 5 (página 296). Lo importante de todo esto es que tanto el proceso de asignación de memoria de stack al comenzar el proceso recursivo hacia adelante (o cascada recursiva), como el proceso de vuelta atrás o backtracking, son gestionados en forma automática por el programa. Lo único que debe hacer el programador es plantear en forma correcta la función, lo cual como ya vimos, implica incluir una condición de corte y efectuar una o mas llamadas recursivas que de alguna forma vayan reduciendo poco a poco el proceso. En nuestro caso, al llamar a factorial() enviando como parámetro el valor n – 1, se va reduciendo el valor con el cual se trabaja hasta que en alguna instancia ese valor será cero y comenzará el proceso de vuelta atrás. 4.] Aplicación elemental de la recursión. El proceso recursivo implica una cascada de invocaciones a nuevas instancias de la misma función, y luego otro proceso de regreso o vuelta atrás mediante el cual se van cerrando los cálculos que estuviesen pendientes en instancias anteriores. El hecho es que no siempre resulta evidente la forma en que ocurre ese proceso de vuelta atrás, sobre todo debido a que el mismo es automático e implícito. Pero si el programador tiene en claro el mecanismo, puede aprovecharlo para lograr resolver problemas que de otro modo parecerían muy complicados. Vemos un ejemplo simple pero muy ilustrativo: Supongamos que se desea implementar una función que simplemente tome como parámetro un número n, y muestre n mensajes en la consola de salida, pero numerados desde 1 hasta n. Supongamos también que se nos pide que la función lo haga en forma recursiva, sin usar un ciclo. Ing. Valerio Frittelli - 295 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Figura 5: Proceso de vuelta atrás completo y finalización de la ejecución. El parámetro queda: n=0 Ejecuta: return 1 Instancia 5 – Finalizada El parámetro queda: n=1 Ejecuta: return 1 * factorial(0) Instancia 4 – Finalizada El parámetro queda: n=2 Ejecuta: return 2 * factorial(1) Instancia 3 – Finalizada El parámetro queda: n=3 Ejecuta: return 3 * factorial(2) Instancia 2 – Finalizada El parámetro queda: n=4 Ejecuta: return 4 * factorial(3) y = factorial(4) Instancia 1 – Finalizada Stack Segment (Memoria de stack) Un primer intento podría verse como sigue: def mostrar01(n): if n > 0: print('Mensaje numero', n) mostrar01(n-1) Evidentemente, si n es cero o menor que cero, la función no tiene nada que hacer (ya que se están pidiendo "cero mensajes"). Por lo tanto, esa es la situación trivial o base que define la condición de corte: la función sólo llevará a cabo algún proceso si n > 0. Si n es mayor que cero, se muestra el primer mensaje incluyendo en él el valor actual de n, y luego se activa la recursión: se vuelve a invocar a la función mostrar01() pero ahora pasándole como parámetro el valor n-1. Al reducir en 1 el valor del parámetro en cada invocación, se garantiza que en algún momento se alcanzará el valor 0 y la cascada recursiva finalizará. Ing. Valerio Frittelli - 296 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Todo parecería correcto… pero el estudiante quizás ya notó que hay un problema: así planteada, la función mostrará efectivamente una secuencia de n mensajes, pero numerados en forma descendente (de n hacia 1) en lugar de hacerlo en forma ascendente (que era lo pedido). Si n es 5, por ejemplo, la salida producida por esta función será: Mensaje numero 5 Mensaje numero 4 Mensaje numero 3 Mensaje numero 2 Mensaje numero 1 En efecto: cada instancia de ejecución de la función chequea si n es mayor a 0. Cuando n vale 5 la condición es cierta, y en la rama verdadera la primera instrucción muestra el valor actual de n, antes de la invocación recursiva. Por lo tanto, era de esperar que el primer mensaje mostrado se numere como 5 y no como 1. En cada una de las otras instancias de ejecución ocurre lo mismo: primero se muestra el valor del parámetro n, y luego de lanza la recursión para los mensajes que quedan. ¿Cómo se podría solucionar el problema y hacer que los mensajes salgan numerados de menor a mayor? Sólo debemos recordar que cada vez que se invoca a la función, se almacena en la memoria de stack el valor del parámetro n. No es obligatorio mostrar el valor de n inmediatamente al entrar en la rama verdadera de la condición: se puede hacer primero la llamada recursiva, ir almacenando con eso en el stack la sucesión de valores (sin mostrarlos), y mostrarlos sólo cuando finaliza la cascada recursiva y a medida que se regresa con el proceso de vuelta atrás: def mostrar02(n): if n > 0: mostrar02(n-1) print('Mensaje numero', n) Por curioso que parezca, esta nueva función hace lo pedido y muestra los mensajes numerados en forma ascendente. Lo único que tuvimos que hacer fue invertir el orden de las instrucciones de la rama verdadera. Como cada vez que se invoca a la función se almacena en la memoria de stack el valor actual de n, pero estos valores se almacenan de forma que el último en llegar es el que queda disponible en la cima del stack, entonces queda en la cima el valor 1 (puede ver la Figura 4 para recordar la forma en que se van generando las instancias de ejecución). Como en nuestra segunda versión las llamadas recursivas se hacen antes que las visualizaciones, el resultado es que ninguna visualización se hará hasta que todas las llamadas recursivas queden almacenadas en el stack… y cuando eso ocurra, la primera instrucción print() en ejecutarse será la que corresponda a la cima del stack que es la que contiene al valor n = 1. El proceso de vuelta atrás hará que se vayan mostrando los valores desde el stack en orden inverso al de su llenado, y eso es lo que hace que los valores se muestren en orden ascendente. La primera función mostrar01() que hemos analizado, tenía una estructura conocida como procesamiento en pre-orden o procesamiento en orden previo, que se caracteriza por el hecho de que el proceso que debe realizar la función (en este caso, el print()), se hace antes que la invocación recursiva. Por otra parte, la función mostrar02() tiene una estructura que se conoce como procesamiento en post-orden o procesamiento en orden posterior: el Ing. Valerio Frittelli - 297 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad proceso a realizar (nuevamente la función print()) se hace después de hacer la invocación recursiva. Para finalizar, un detalle: el segmento de memoria que hemos llamado Stack Segment se designa con ese nombre por una razón de peso: la palabra en inglés stack se traduce como pila en español y ese nombre se debe a que en ese segmento los valores que se almacenan van apilándose uno sobre otro a medida que se van invocando funciones (con recursión o no) (vuelva a ver la Figura 4 para observar este efecto). Y como ya vimos en una Ficha anterior, esta forma de almacenar datos se conoce como esquema de Pila o de tipo LIFO por sus iniciales en inglés: Last In – First Out (Primero en llegar – Último en salir). El Stack Segment es el segmento de soporte para todos los procesos de invocaciones a funciones de cualquier lenguaje de programación. Cada vez que se invoca a una función, se reserva para ella un espacio en la cima del stack y en ese espacio la función almacena la dirección a la que se debe volver cuando finalice su ejecución, y sus variables locales. Y cuando una función finaliza, se libera el espacio de stack que la misma tenía, quedando en la cima la función desde la cual se invocó a la que acaba de terminar. Y es natural que funcione como un apilamiento de datos: cuando una función termina, el flujo de ejecución del programa debe regresar al punto desde donde fue invocada la que acaba de terminar, y es justamente esa la que en ese momento estará en la cima. El Stack Segment constituye así un mecanismo confiable para que el programa recuerde el camino de regreso que debe seguir a medida que las funciones que se invocaron vayan finalizando. 5.] Consideraciones generales. Llegado a este punto quizá resulte obvio que la recursividad es un proceso algo complicado de entender para quienes recién se acercan a ella. Sin embargo es también cierto que después de un poco de práctica el proceso se asimila sin inconvenientes, sobre todo si en ese período de práctica el lector se toma el trabajo de hacer un seguimiento gráfico de las funciones recursivas que plantea. Uno de los puntos que más trabajo parece costar a los recién iniciados es el planteo de la condición de corte de la función (es decir, la condición para evitar la recursión infinita). La clave de este paso es tener en cuenta que lo que se busca determinar con esa condición es si se ha presentado lo que se conoce como un caso base o un caso trivial para el problema: un caso en el que la recursión no es necesaria y puede resolverse en forma directa (o incluso no haciendo nada). La determinación de esa condición de corte puede hacerse sin mayores problemas, simplemente respondiendo a la siguiente pregunta: ¿En qué caso o casos el problema que se quiere plantear se resuelve en forma trivial? La respuesta a esa pregunta, aplicada al problema particular que se está enfrentando evidencia la condición de corte que se buscaba. En el caso del cálculo del factorial, la pregunta sería: ¿en qué caso el factorial de n se resuelve en forma trivial, sin necesidad de cálculos ni procesos recursivos? Es obvio que ese caso se da cuando n vale cero, pues entonces el factorial vale directamente 1 (uno). Y en nuestra versión recursiva del factorial hemos incluido entonces una condición de corte que comprueba si n es 0. Por otra parte, debe observarse que la recursividad es una herramienta para usar con cautela : si bien es cierto que una función recursiva es extremadamente compacta en Ing. Valerio Frittelli - 298 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad cuanto a código fuente y permite además que una definición recursiva sea llevada a una función recursiva prácticamente sin cambios (obsérvese la gran similitud que existe entre la definición algebraica recursiva del factorial y el planteo de la función para calcular el factorial), también es cierto que la recursividad insume más memoria que la que usaría un proceso cíclico común. Esto se debe a que cada instancia recursiva pide memoria de stack para esa instancia (como se vio en los gráficos anteriores). Si la cascada recursiva fuera muy larga (por ejemplo, para calcular el factorial de un número grande), podría llegar a provocarse un rebalsamiento, desborde o sobreflujo (overflow) de memoria de stack. Esto significa que alguna instancia de la cascada de invocaciones podría no tener lugar en el Stack Segment para ejecutarse, con lo cual se produciría la interrupción o cancelación del programa que invocó a esa función. La memoria de un computador es un recurso de tamaño limitado, y el Stack Segment es parte de la memoria. Por otra parte, la ejecución de una función requiere cierto tiempo de procesamiento desde que esta comienza y hasta que finaliza, que debe contemplarse en la estimación del tiempo total de ejecución de un proceso recursivo completo. En el caso del factorial, la versión iterativa (no recursiva, basada en ciclos) tendrá un tiempo de ejecución en relación directa con el tiempo que demore el ciclo for en finalizar, y este ciclo depende a su vez del valor de n. Por otra parte, la versión recursiva hará tantas invocaciones recursivas como sea el valor de n, y el tiempo total dependerá del tiempo que lleve terminar de ejecutar cada una. En este caso, se puede asumir que en ambos escenarios se tendrá un tiempo de ejecución que depende de n en forma directa, y por lo tanto serían igualmente aceptables la versión recursiva y la versión iterativa. Notemos además que el código fuente de la versión recursiva es simple, directo y compacto. La complejidad aparente y la estructura del código fuente de un programa o función es otro de los elementos que se suelen tener en cuenta para hacer un análisis comparativo entre dos o más soluciones propuestas para un mismo problema. Pero en el caso del factorial, la versión iterativa no es mucho más compleja que la recursiva, aunque es cierto que la recursiva es más directa para comprender. Si se tienen en cuenta los tres factores generales de análisis comparativo entre algoritmos (consumo de memoria, tiempo de ejecución y complejidad de código fuente) entonces si un programador debe realizar al cálculo del factorial de n, debería usar la versión iterativa (y no la recursiva). La decisión final de usar la versión iterativa, se basa en este caso en el uso más eficiente de la memoria por parte de la versión iterativa. El tiempo de ejecución final está en el mismo orden de magnitud en ambos casos y la complejidad del código fuente es aceptable también en ambos casos. Por estos motivos, en general se suele aconsejar usar la recursividad sólo cuando sea absolutamente necesario por la naturaleza implícitamente recursiva del problema que se enfrenta, como es el caso del recorrido de ciertas estructuras de datos como los árboles o los grafos, o la generación de gráficos de naturaleza fractal (figuras que se forman combinando versiones más sencillas de las mismas figuras…) que resultaría muy difícil de programar sin recursión desde el punto de vista de la complejidad del código fuente. Algunos programadores experimentados a veces plantean primero la solución recursiva de un problema (para darse una idea de la forma mínima de resolverlo desde el punto de vista Ing. Valerio Frittelli - 299 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad de la complejidad del código fuente), y luego tratan de convertir ese planteo a una solución no recursiva basada en ciclos (aunque esto no siempre es sencillo de hacer…) 6.] Caso de análisis: La Sucesión de Fibonacci. Para permitir un mayor dominio de las técnicas de programación recursiva, y sus ventajas y desventajas, analizaremos ahora un conocido problema: el cálculo del término n-ésimo de la Sucesión de Fibonacci. Problema 34.) La Sucesión de Fibonacci es una secuencia de valores naturales en la que cada término es igual a la suma de los dos anteriores, asumiendo que el primer y el segundo término valen 1. En algunas fuentes se parte de suponer que los dos primeros valen 0 y 1 respectivamente, pero eso no cambia el espíritu de la regla ni la explicación que sigue. Formalmente, el cálculo del término n-ésimo F(n) de la sucesión se puede entonces definir así (y note que la definición planteada es directamente recursiva): Término n-ésimo de Fibonacci =1 (si n = 1 ó n = 0) F(n) (n entero, n >= 0) = F(n-1) + F(n-2) (si n >1) Se pide desarrollar un programa que permita calcular el valor del término enésimo de esta sucesión, cargando n por teclado. Discusión y solución: Si bien el enunciado muestra la definición en forma directamente recursiva, podemos diseñar un par de funciones que calculen el valor del término n-ésimo de Fibonacci: una en forma iterativa y la otra en forma recursiva para luego poder comparar ambas soluciones (vea el proyecto F Recursión que acompaña a esta ficha): # versión iterativa def fibonacci01(n): ant2 = ant1 = 1 for i in range(2, n + 1): aux = ant1 + ant2 ant2 = ant1 ant1 = aux return ant1 # versión recursiva def fibonacci02(n): if n 0: # dibujar recursivamente el soporte inferior izquierdo... pyramid(canvas, x-r, y+r, r//2) # dibujar recursivamente el soporte inferior derecho... pyramid(canvas, x+r, y+r, r//2) # dibujar recursivamente el soporte superior izquierdo... pyramid(canvas, x-r, y-r, r//2) # dibujar recursivamente el soporte superior derecho... pyramid(canvas, x+r, y-r, r//2) # dibujar en (post-orden) la tapa o cima de la pirámide... square(canvas, x, y, r) def square(canvas, x, y, r): left = x - r top = y - r Ing. Valerio Frittelli - 307 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad right = x + r down = y + r canvas.create_rectangle((left, top, right, down), outline='yellow', fill='blue') def render(): # configuracion inicial de la ventana principal... root = Tk() root.title("Piramide Fractal") # calculo de resolucion en pixels de la pantalla... maxw = root.winfo_screenwidth() maxh = root.winfo_screenheight() # ajustar dimensiones y coordenadas de arranque de la ventana... root.geometry("%dx%d+%d+%d" % (maxw, maxh, 0, 0)) # un lienzo de dibujo dentro de la ventana... canvas = Canvas(root, width=maxw, height=maxh) canvas.grid(column=0, row=0) # sea valor inicial de r igual a un duodécimo del ancho de la pantalla... r = maxw // 12 # coordenadas del centro de la pantalla... cx = maxw // 2 cy = maxh // 2 # dibujar piramide centrada en (cx, cy) y el cuadrado mayor con lado = 2r. pyramid(canvas, cx, cy, r) # lanzar el ciclo principal de control de eventos de la ventana... root.mainloop() if __name__ == '__main__': render() El programa comienza con una instrucción import para dar acceso al contenido del módulo tkinter, que es el que básicamente contiene las declaraciones y funciones para manejar ventanas y gráficos: from tkinter import * La función pyramid() es la que realiza el gráfico completo de la pirámide usando recursión, pero veremos primero la forma de dibujar un cuadrado simple. La función square(canvas, x, y, r) es la encargada simplemente de dibujar un cuadrado de bordes amarillos y pintado por dentro de color azul. def square(canvas, x, y, r): left = x - r top = y - r right = x + r down = y + r canvas.create_rectangle((left, top, right, down), outline='yellow', fill='blue') El parámetro canvas recibido por la función, es el lienzo o área de dibujo en donde debe graficarse el cuadrado (por el momento, no es necesario saber de dónde sale ese lienzo: simplemente, la función square() lo toma como parámetro y dibuja en él el cuadrado pedido). Ing. Valerio Frittelli - 308 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Los parámetros x e y son las coordenadas de columna y fila (respectivamente) del pixel que queremos que sea el centro del cuadrado dentro del canvas donde será dibujado. Y el parámetro r es el valor de la mitad de la longitud del lado del cuadrado a dibujar (en pixels), por lo que la longitud total del lado será igual a 2*r. Las cuatro primeras líneas de la función square() calculan entonces las coordenadas de pixel de las esquinas superior izquierda e inferior derecha del cuadrado (asignando esos valores en las variables (left, top) y (right, down)) (asegúrese de entender la naturaleza de estos cuatro cálculos). Finalmente, en la última línea de la función square(), se invoca a la función canvas.create_rectangle() para dibujar el cuadrado. Un elemento u objeto de tipo Canvas dispone de funciones (o métodos) para dibujar distintos tipos de figuras básicas o primitivas. En este caso, el método create_rectangle((left, top, right, down), outline='yellow', fill='blue' ) recibe como primer parámetro una tupla conteniendo los valores de las coordenadas de los pixels superior izquierdo e inferior derecho del rectángulo a dibujar. El parámetro outline (accedido por palabra clave) indica el color con el que será dibujado el borde o perímetro del rectángulo (aquí lo asignamos en amarillo ('yellow')). Y el parámetro fill (también accedido por palabra clave) indica el color con el que será pintado por dentro el rectángulo (y aquí lo asignamos en azul ('blue')). Note que esta función no dibuja la pirámide: sólo dibuja un cuadrado en las coordenadas centrales (x, y) que se le indiquen y con longitud de su lado igual a 2r. Es la función pyramid() la que dibuja toda la pirámide, aplicando recursión e invocando tantas veces como sea necesario a la función square(). La definición recursiva del concepto de "pirámide formada por cuadrados" puede enunciarse intuitivamente así: "Una pirámide formada por cuadrados de lado máximo 2r estará vacía si r es 0 (no se puede dibujar un lado de longitud 0), o bien contendrá un cuadrado de lado 2r en la cima que estará apoyado en cuatro soportes. Pero estos cuatro soportes serán a su vez pirámides formadas por cuadrados cuyos lados serán de longitud máxima r." Claramente esta definición es recursiva: el concepto de pirámide aparece en la propia definición. Pues bien: se trata de dibujar una pirámide formada por cuatro pirámides menores (los soportes) y un cuadrado en la cima. Y eso es exactamente lo que hace la función pyramid(canvas, x, y, r) (los parámetros tienen el mismo significado que en la función square()): def pyramid(canvas, x, y, r): if r > 0: # dibujar recursivamente el soporte inferior izquierdo... pyramid(canvas, x-r, y+r, r//2) # dibujar recursivamente el soporte inferior derecho... pyramid(canvas, x+r, y+r, r//2) # dibujar recursivamente el soporte superior izquierdo... pyramid(canvas, x-r, y-r, r//2) # dibujar recursivamente el soporte superior derecho... pyramid(canvas, x+r, y-r, r//2) # dibujar en (post-orden) la tapa o cima de la pirámide... square(canvas, x, y, r) Ing. Valerio Frittelli - 309 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad La situación trivial se da cuando r es 0: en ese caso la función simplemente termina sin hacer nada. Pero si r es mayor a 0 (la longitud del lado del cuadrado es por lo menos 2*1 = 2), entonces se procede al dibujado "desde abajo y hacia la cima", con cuatro invocaciones recursivas (una para cada soporte). Usamos recursión pues tenemos que dibujar cuatro pirámides que sostengan a la pirámide mayor… Los valores x, y, r enviados como parámetro a cada instancia recursiva de la función pyramid() se calculan de forma que cada nueva pirámide se dibuje con diferentes coordenadas del centro y una longitud 2r para el lado del cuadrado en la cima progresivamente menor, dividiendo por 2 a r en cada invocación. Esta sucesión de divisiones en algún momento hará que se llegue a un valor de r que será igual a 0, y en ese momento se detendrá la recursión. Observe un detalle: las cuatro invocaciones recursivas se hacen antes que la invocación a la función square()… lo cual tiene sentido, ¡ya que primero deben construirse las paredes antes de colocar el techo! Formalmente, como el proceso de dibujar el cuadrado se hace después que terminan las invocaciones recursivas, entonces tenemos un proceso de dibujado en post-orden() (u orden posterior). La última función que queda en el programa es render(), y es la encargada de preparar el contexto visual y gráfico: def render(): # configuracion inicial de la ventana principal... root = Tk() root.title("Piramide Fractal") # calculo de resolucion en pixels de la pantalla... maxw = root.winfo_screenwidth() maxh = root.winfo_screenheight() # ajustar dimensiones y coordenadas de arranque de la ventana... root.geometry("%dx%d+%d+%d" % (maxw, maxh, 0, 0)) # un lienzo de dibujo dentro de la ventana... canvas = Canvas(root, width=maxw, height=maxh) canvas.grid(column=0, row=0) # sea valor inicial de r igual a un duodécimo del ancho de la pantalla... r = maxw // 12 # coordenadas del centro de la pantalla... cx = maxw // 2 cy = maxh // 2 # dibujar piramide centrada en (cx, cy) y el cuadrado mayor con lado = 2r. pyramid(canvas, cx, cy, r) # lanzar el ciclo principal de control de eventos de la ventana... root.mainloop() Prácticamente todas las novedades técnicas para la creación y control de la ventana principal y el canvas están en esta función. La primera instrucción crea una variable que hemos llamado root con la función Tk(). Una variable de tipo Tk representa una ventana básica, con bordes definidos, barra de título y controles de minimización y cierre de la ventana. La variable root será entonces la que nos permitirá controlar lo que ocurre con la ventana donde se despliega el gráfico. Y la segunda instrucción simplemente asigna la cadena de caracteres que será visualizada en la barra de título de esa ventana: Ing. Valerio Frittelli - 310 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad # configuracion inicial de la ventana principal... root = Tk() root.title('Piramide Fractal') Las siguientes dos líneas permiten básicamente averiguar la resolución (en pixels) de la pantalla en el momento de ejecutar el programa, para poder luego calcular en forma correcta las dimensiones de la ventana y, sobre todo, las coordenadas del pixel central: # calculo de resolucion en pixels de la pantalla... maxw = root.winfo_screenwidth() maxh = root.winfo_screenheight() La función winfo_screenwidth() retorna el ancho máximo en pixels admitido por la resolución actual de la pantalla, y la función winfo_screehight() hace lo mismo pero con la altura. Al momento de ejecutar este programa para preparar esta Ficha, la resolución era de 1366 pixels de ancho por 768 pixels de alto, y esos dos valores (o los que correspondan) se almacenan en las variables maxw y maxh. La quinta línea del programa ajusta lo que se conoce como la geometría de la ventana principal (que como vimos, tenemos representada con la variable root): # ajustar dimensiones y coordenadas de arranque de la ventana... root.geometry('%dx%d+%d+%d' % (maxw, maxh, 0, 0)) La función geometry() permite ajustar el ancho y el alto de la ventana en cualquier momento, y también las coordenadas del pixel superior izquierdo desde donde debe mostrarse esa ventana. La función toma como parámetro una cadena de caracteres de la forma 'WxH+x+y' en la que W es el ancho en pixels que queremos que tenga la ventana al mostrarse, H es la altura en pixels para la ventana, x es la coordenada de columna del pixel superior izquierdo donde queremos que aparezca, e y es la coordenada de fila de ese mismo pixel. A modo de ejemplo simple, si hubiésemos hecho algo como: root.geometry('400x300+50+50') entonces la ventana representada por la variable root tomaría un ancho de 400 pixels, una altura de 300 pixels, y sería visualizada con su esquina superior izquierda en el pixel de coordenadas (50, 50) de la pantalla. El problema es que en muchos casos los valores que se quieren asignar están contenidos en variables y no vienen como constantes directas. En nuestro programa, por ejemplo, queremos que la ventana aparezca con un ancho tan grande como el que se tenga disponible en la resolución actual (y como vimos, tenemos ese valor almacenado en la variable maxw) y lo mismo vale para la altura (que tenemos en maxh). Si quisiéramos esos valores ancho y alto, y hacer aparecer la ventana desde el pixel (0, 0), entonces una invocación de la forma: root.geometry('maxw x maxh + 0+0') simplemente provocaría un error al ejecutarse: la cadena contiene letras donde Python esperaba encontrar dígitos… La forma de tomar esos valores desde variables, consiste en usar caracteres de reemplazo (también llamados caracteres de formato) en la cadena. El par de caracteres %d se toma como si fuese un único caracter, y se interpreta como que en ese lugar debe ir el valor de Ing. Valerio Frittelli - 311 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad una variable de tipo entero (int) que se informa más adelante en la propia lista de parámetros de la función. En nuestro programa, la función se está invocando así: root.geometry('%dx%d+%d+%d' % (maxw, maxh, 0, 0)) lo cual significa que el primer caracter %d (marcado en rojo en el ejemplo) será reemplazado por el valor de la variable maxw que es a su vez la primera en la tupla que aparece luego del signo % (de color negro). En forma similar, el segundo %d (azul) será reemplazado por el valor de la variable maxh, que es la segunda en la tupla, y así hasta el final. Las dos instrucciones siguientes asignan una variable que hemos llamado canvas con un elemento u objeto de tipo Canvas para hacer allí los gráficos que necesitamos: # un lienzo de dibujo dentro de la ventana... canvas = Canvas(root, width=maxw, height=maxh) canvas.grid(column=0, row=0) La función Canvas() crea un objeto que representa un lienzo de dibujo. Esa función toma varios parámetros, y en este caso el primero es la variable root que representa nuestra ventana principal. Al enviar la ventana como parámetro, le estamos indicando al programa que el Canvas que estamos creando (variable canvas) estará contenido en esa ventana (variable root) y por eso todo lo que se dibuje en canvas, aparecerá en la ventana root. Los otros dos parámetros que estamos enviando a la función Canvas() se están accediendo por palabra clave, e indican el ancho y el alto en pixels que debe tener el canvas dentro de la ventana. En este caso, simplemente hemos asumido que el canvas será el único elemento contenido en la ventana root, y le hemos fijado un ancho y un alto máximo (los valores de nuestras variables maxw y maxh). Por supuesto, esto puede ajustarse a voluntad del programador. Cuando una ventana es creada, todos los elementos que se incluyan dentro de ella serán distribuidos en filas y columnas, como si el interior de la ventana fuese una tabla. La invocación a la función grid() que sigue a la creación del canvas, le dice al programa que el canvas debe ser ubicado dentro de la ventana en la "casilla" indicada por los parámetros column y row (en este caso, la casilla [0, 0]). La instrucción que sigue sólo calcula el valor inicial para r, la mitad de la longitud del lado del cuadrado mayor que irá en la cima de la pirámide: # sea un valor inicial de r igual a un duodécimo del ancho del area de dibujo... r = maxw // 12 En este caso, se está tomando un valor igual a la duodécima parte del valor del ancho máximo para la ventana. El estudiante puede cambiar el 12 por otro valor y explorar los efectos que eso produce. Las dos instrucciones que siguen simplemente calculan las coordenadas del centro de la pantalla: # coordenadas del centro de la pantalla... cx = maxw // 2 cy = maxh // 2 Ing. Valerio Frittelli - 312 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Estas coordenadas son importantes para nuestro programa, ya que le indican en qué posición del canvas de la ventana deberá estar centrada la vista de la pirámide, y a partir de esa posición la pirámide se irá construyendo hacia afuera. La anteúltima instrucción invoca a la función pyramid() para dibujar la pirámide completa, cuyo funcionamiento recursivo ya hemos explicado más arriba: # dibujar piramide centrada en (cx, cy) y el cuadrado mayor con lado = 2r. pyramid(canvas, cx, cy, r) Sólo note que el parámetro canvas es el lienzo de dibujo que hemos creado dentro de la ventana, y que la función pyramid() lo recibe justamente para poder desarrollar en él nuestro gráfico. Finalmente, la última instrucción es la que efectivamente pone todo a funcionar: # lanzar el ciclo principal de control de eventos de la ventana... root.mainloop() La ventana representada por la variable root se usa para invocar al método mainloop(), el cual hace que la ventana se muestre y quede a disposición del usuario. Toda acción que ese usuario aplique sobre la ventana (pasar el mouse sobre ella, minimizarla, presionar el botón de cierre, etc.) genera en el programa lo que se conoce como un evento, y el método mainloop() se encarga de tomar todos los eventos producidos por la ventana root y procesarlos adecuadamente. Por caso, es el método mainloop() el que cierra la ventana y da por terminado el programa cuando el usuario presione el botón de cierre ubicado arriba y a la derecha de la ventana. 9.] Pruebas y aplicaciones. El programa que hemos mostrado en la sección anterior puede ser modificado de distintas maneras para producir diferentes (y muy interesantes) resultados gráficos. Nos permitimos mostrar más abajo algunas gráficas que hemos generado con algunas de esas variantes, y sugerimos al estudiante a que explore y aprenda en qué formas podría generar las mismas figuras efectuando distintos cambios en el código fuente original. Diviértase… Figura 11: Gráficas producidas con modificaciones simples del programa [F14] Piramide [Parte 1] a.) b.) c.) Ing. Valerio Frittelli - 313 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad Figura 12: Gráficas producidas con modificaciones no tan simples del programa [F14] Piramide [Parte 2] a.) b.) Figura 13: Gráficas producidas con modificaciones no tan simples del programa [F14] Piramide [Parte 3] a.) b.) c.) Ing. Valerio Frittelli - 314 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad 10.] La Función de Ackermann. La Función de Ackermann es una función recursiva matemática que debe su nombre a quien la postuló en 1926: Wilhelm Ackermann. La Función de Ackermann se basa en aplicar un operador simple (la suma) combinado con numerosas invocaciones recursivas, con la intención de lograr un crecimiento muy rápido en la magnitud de los valores calculados. Toda la explicación necesaria para comprender su uso y la forma de programarla, se expone en el problema que sigue:5 Problema 35.) La Función de Ackermann originalmente planteada por Wilhelm Ackermann en 1926 ha sido ajustada a lo largo de los años hasta terminar siendo definida en la forma que se muestra aquí: Función de Ackermann =n+1 (si m = 0) A(m, n) = A(m – 1 , 1) (si m > 0 y n == 0) (m, n enteros = A(m – 1, A(m, n – 1)) (si m > 0 y n > 0) m >=0, n >= 0) Se pide desarrollar un programa que permita calcular el valor de la Función de Ackermann para distintos valores de m y n. Discusión y solución: La función originalmente planteada por Ackermann tenía tres parámetros en lugar de dos. Como dijimos, a lo largo de los años se han ido sugiriendo variantes y modificaciones que terminaron conformando una familia o serie de funciones de Ackermann, basadas en estructuras similares. La definición que mostramos en el enunciado es una variante que fue propuesta por Rózsa Peter y Raphael Robinson, aunque es común que se la cite como si fuese la original de Ackermann. En algunos contextos, la variante de Peter y Robinson se conoce también como la Función de Ackermann-Peter. La función está definida directamente en forma recursiva, por lo que su programación también es directa y no ofrece mayores problemas (ver el proyecto F Ackermann que acompaña a esta Ficha): def ackermann(m, n): if m == 0: return n + 1 elif n == 0: return ackermann(m - 1, 1) else: return ackermann(m - 1, ackermann(m, n - 1)) Técnicamente hablando, el problema está resuelto. Sin embargo, conviene tomarse un tiempo para estudiar esta función y sus propiedades. Lo primero que se observa es que sólo la primera parte de la definición es no recursiva: si m = 0 entonces A(0, n) = n + 1. Esto significa que lo que sea que termine calculando, será el resultado de aplicar ese único operador directo (la suma), para añadir 1 al valor de n. El siguiente programa (incluido en el mismo proyecto F Ackermann) calcula diversos valores para la función haciendo que m tome todo valor posible en el intervalo [0, 3] y n tome valores del intervalo [0, 6]: 5 La fuente esencial de la explicación que sigue sobre la Función de Ackermann, es la Wikipedia (especialmente la versión en inglés): https://en.wikipedia.org/wiki/Ackermann_function. También hemos usado una referencia básica contenida en el libro "Estructuras de Datos con C y C++" de Yedidyah Langsam (y otros), así como alguna cita del libro "Estructuras de Datos en Java" del ya citado Mark Allen Weiss. Ing. Valerio Frittelli - 315 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad def test(): for m in range(4): for n in range(7): ack1 = ackermann(m, n) print('Ackermann(', m, ', ', n, '): ', ack1, '\t-\t', sep='', end='') print() test() Podría parecer entonces que la función entregará resultados que no serán de valor muy alto, ya que todos los cálculos se hacen en base a sumar 1 al valor actual de n en cada instancia recursiva. Pero la realidad es que para valores combinados de m y n relativamente bajos, la función llega a resultados asombrosamente elevados. Mientras el valor de m se mantenga menor a 4 y el valor de n se mantenga menor a 7, la función devuelve valores de magnitud aceptable, como se puede ver en la siguiente salida generada por el programa anterior: A(0,0): 1 A(0,1): 2 A(0,2): 3 A(0,3): 4 A(0,4): 5 A(0,5): 6 A(0,6): 7 A(1,0): 2 A(1,1): 3 A(1,2): 4 A(1,3): 5 A(1,4): 6 A(1,5): 7 A(1,6): 8 A(2,0): 3 A(2,1): 5 A(2,2): 7 A(2,3): 9 A(2,4): 11 A(2,5): 13 A(2,6): 15 A(3,0): 5 A(3,1): 13 A(3,2): 29 A(3,3): 61 A(3,4): 125 A(3,5): 253 A(3,6): 509 Si el valor inicial de m es 0, la función directamente retorna n + 1, y eso produce que la primera fila de la tabla anterior simplemente contenga la progresión de los números naturales para los resultados. Las dos filas que siguen se mantienen con valores de salida pequeños. Pero la cuarta fila ya comienza a producir resultados bastante mayores. Para A(3,5) el resultado ya es 253 y para A(3, 6) se obtiene un 509. Evidentemente, cuando los valores combinados de m y n comienzan a crecer, la función realiza una cantidad muy alta de invocaciones recursivas, y eso hace que el valor de salida sea muy alto también (aunque se obtenga sólo con la acción de sumar 1…) Si intentamos calcular A(3,7) el programa se interrumpe por overflow de stack sin llegar a mostrarnos el resultado: la cantidad de instancias recursivas es tan grande que no puede ser soportada por el Stack Segment. Lo anterior lleva a que nos preguntemos si la función está efectivamente bien planteada, o si por el contrario, pudiera estar entrando en una situación de recursión infinita que sea la responsable del overflow de stack. Al fin y al cabo, no parece evidente que A(m,n) llegue a terminar de calcularse alguna vez para valores de m y n bastante mayores que 0, ya que la segunda parte de la definición de la función hace una llamada recursiva, pero la tercera hace algo más complejo aún: una invocación recursiva compuesta con otra (la primera toma como parámetro al resultado de la segunda, haciendo una composición de funciones). Sin embargo, un análisis detallado del comportamiento de la función nos lleva a concluir que la función está bien planteada y no produce una regresión infinita: si m y n son diferentes de cero, ambos son restados en 1 en algún momento durante la cascada recursiva, pero se comienza restando 1 a n. Cuando el valor de n llega a ser 0, comienza desde allí a restarse 1 a m, lo que eventualmente llevará a m = 0 y a la detención de la cascada recursiva. El tema es que hasta que eso ocurra, se creará una inmensa cantidad de instancias recursivas que hará que los valores retornados sean cada vez mayores, y provocando también el rebalsamiento de stack. Para terminar de comprender la magnitud de los valores que llega a calcular la función, note que A(4,0) vale 13. El valor A(4,1) ya pasa a ser 65333 (aunque nuestra función posiblemente ya no pueda calcularlo por producirse un overflow de stack). Y el valor A(4,2) es tan inmenso que no puede escribirse sino en forma exponencial: ese valor es igual a 2 65536 – 3 (de hecho, este número resulta ser mayor que u200 donde u es la cantidad total de partículas contenidas Ing. Valerio Frittelli - 316 Cátedra de AED [Ciclo 2024] Ficha 14: Recursividad en el universo). Y se pone mucho peor: los valores de la función para m > 4 y n > 1 son tan extravagantemente enormes que no podrían escribirse nunca en forma normal, ya que la secuencia de dígitos que conforma a cada uno de esos números no cabe en el universo conocido (y por supuesto, ni nuestro programa ni ningún otro podría siquiera comenzar a calcular esos valores, ya que mucho antes de llegar al final se produciría un overflow de stack). Para finalizar, digamos que la Función de Ackermann tiene ciertos usos prácticos: por lo pronto, debido a su naturaleza profundamente recursiva, puede utilizarse para testear la habilidad de un compilador en optimizar un proceso recursivo. En general, cuando se compila un programa recursivo, el compilador intenta eliminar la recursión y producir una versión compilada iterativa, que será más eficiente en cuanto a uso de memoria y posiblemente en velocidad de ejecución. La Función de Ackermann puede ser entonces uno de los desafíos que se le imponen a un compilador cuando esté en etapa de prueba (o benchmarking). Además, dado que la Función de Ackermann tomada para m = n (o sea: A(n,n), que a su vez puede simplificarse como A(n)) crece de forma tan violenta, entonces su inversa (es decir, la función que a cada número y calculado por A(n) le asigna el mismo valor n de partida) normalmente designada con la letra griega alfa: α(n) = A-1(n) aumenta de manera sorprendentemente lenta. De hecho, la función α(n) retorna valores menores que 5 para prácticamente cualquier valor de n que se tome como parámetro. Esta propiedad de la inversa de Ackermann de crecer tan lentamente, suele usarse en el contexto del análisis de algunos algoritmos que se sabe que tienen un tiempo de ejecución que crece de forma muy lenta a medida que aumenta el número de datos. Bibliografía V. Frittelli, Algoritmos y Estructuras de Datos, Córdoba: Universitas, 2001. Python Software Foundation, "Python Documentation," 2015. [Online]. Available: https://docs.python.org/3/. [Accessed 24 February 2015]. R. Sedgewick, Algoritmos en C++, Reading: Addison Wesley - Díaz de Santos, 1995. M. A. Weiss, Estructuras de Datos en Java - Compatible con Java 2, Madrid: Addison Wesley, 2000. M. Pilgrim, "Dive Into Python - Python from novice to pro," 2004. [Online]. Available: http://www.diveintopython.net/toc/index.html. [Accessed 6 March 2015]. V. Frittelli, R. Teicher, M. Tartabini, J. Fernández and G. F. Bett, "Gestión de Gráficos (en Java) para Asignaturas de Programación Introductiva," in Libro de Artículos Presentados en I Jornada de Enseñanza de la Ingeniería - JEIN 2011, Buenos Aires, 2011. Wikipedia, "Ackermann function," 2015. [Online]. Available: https://en.wikipedia.org/wiki/Ackermann_function. Y. Langsam, M. Augenstein and A. Tenenbaum, Estructura de Datos con C y C++, México: Prentice Hall, 1997. Ing. Valerio Frittelli - 317 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento Ficha 22 Ordenamiento 1.] Algoritmos de ordenamiento. Clasificación tradicional. Es claro que pueden existir muchos algoritmos diferentes para resolver el mismo problema, y el problema de la ordenación de un arreglo es quizás el caso emblemático de esa situación. Podemos afirmar que existen varias docenas de algoritmos diferentes para lograr que el contenido de un arreglo se modifique para dejarlo ordenado de menor a mayor, o de mayor a menor. Muchos de esos algoritmos están basados en ideas intuitivas muy simples, y otros se fundamentan en estrategias lógicas muy sutiles y no tan obvias a primera vista. En general, se suele llamar algoritmo simples o algoritmos directos a los del primer grupo, y algoritmos compuestos o algoritmos mejorados a los del segundo, aunque la diferencia real entre ambos no es sólo conceptual, sino que efectivamente existe una diferencia de rendimiento muy marcada en cuanto al tiempo que los algoritmos de cada grupo demoran en terminar de ordenar el arreglo. Más adelante profundizaremos la cuestión del análisis comparativo del rendimiento de algoritmos, y justificaremos formalmente la diferencia entre los dos grupos, pero por ahora nos concentraremos sólo en la clasificación de los algoritmos y el funcionamiento de aquellos que estén al alcance de este curso. Tradicionalmente, como dijimos, los algoritmos de ordenamiento se suelen clasificar en los dos grupos ya citados, y en cada grupo se encuentran los siguientes (aunque entienda: la tabla siguiente es sólo una forma clásica de presentar a los algoritmos más conocidos, pero estos no son todos los algoritmos que existen… que son varias docenas…) : Figura 1: Clasificación tradicional de los algoritmos de ordenamiento más comunes. Algoritmos Simples o Directos Algoritmos Compuestos o Mejorados Intercambio Directo (Burbuja) Método de Ordenamiento Rápido (Quicksort) [C. Hoare - 1960] Selección Directa Ordenamiento de Montículo (Heapsort) [J. Williams – 1964] Inserción Directa Ordenamiento por Incrementos Decrecientes (Shellsort) [D. Shell – 1959] En principio, los algoritmos clasificados como Simples o Directos son algoritmos sencillos e intuitivos, pero de mal rendimiento si la cantidad n de elementos del arreglo es grande o muy grande, o incluso si lo que se desea es ordenar un archivo en disco. Aquí, mal rendimiento por ahora significa "demasiada demora esperada". En cambio, los métodos presentados como Compuestos o Mejorados tienen un muy buen rendimiento en comparación con los simples, y se aconsejan toda vez que el arreglo sea muy grande o se quiera ordenar un conjunto en memoria externa. Si el tamaño n del arreglo es pequeño (por ejemplo, no más de 100 o 150 elementos), los métodos simples siguen siendo una buena elección por cuanto su escasa eficiencia no es notable con conjuntos pequeños. Note que la idea final, es que cada algoritmo compuesto mostrado en esta tabla representa en realidad una mejora en el planteo del algoritmo simple de la misma fila, y por ello se los llama "algoritmos mejorados". Así, el algoritmo Quicksort es un replanteo del algoritmo de intercambio directo (más conocido como ordenamiento de burbuja) para eliminar los Ing. Valerio Frittelli - 436 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento elementos que lo hacen ineficiente. Paradójicamente, el ordenamiento de burbuja o bubblesort es en general el de peor rendimiento para ordenar un arreglo, pero ha dado lugar al Quicksort, que en general es el de mejor rendimiento promedio conocido. 2.] Funcionamiento de los Algoritmos de Ordenamiento Simples o Directos. Haremos aquí una breve descripción operativa de las estrategias de funcionamiento de los algoritmos directos conocidos como Intercambio Directo (o Burbuja o Bubblesort) e Inserción Directa. Para una descripción del algoritmo de Selección Directa, revise la Ficha 16. Más adelante, en una Ficha posterior, mostraremos un análisis de rendimiento formal basado en calcular la cantidad de comparaciones que estos algoritmos realizan. En todos los casos, suponemos un arreglo v de n elementos, y también suponemos que se pretende ordenar de menor a mayor. Hemos incluido un modelo llamado test01.py en el proyecto [F22] Ordenamiento, que acompaña a esta Ficha. En el mismo proyecto se incluye el módulo ordenamiento.py, que contiene todas las funciones que implementan estos algoritmos. a.) Ordenamiento por Intercambio Directo (o Bubblesort): La idea esencial del algoritmo es que cada elemento en cada casilla v[i] se compara con el elemento en v[i+1]. Si este último es menor, se intercambian los contenidos. Se usan dos ciclos anidados para conseguir que incluso los elementos pequeños ubicados muy atrás, puedan en algún momento llegar a sus posiciones al frente del arreglo. Gráficamente, supongamos que el tamaño del arreglo es n = 4. El algoritmo procede como se muestra en la Figura 2. Figura 2: Funcionamiento general del Ordenamiento por Intercambio Directo (Bubblesort). n=4 primera pasada: el 7 se compara con el 3 y se intercambia. Luego se compara con el 5 y también se intercambia. Y finalmente se compara con el 2 y se vuelve a 7 3 5 2 intercambiar, quedando en su posición final. 0 1 2 3 segunda pasada: el 7 ya está ordenado, por lo cual se repite el esquema desde el principio pero con una comparación menos al final. Ahora el 3 se compara con el 3 5 2 7 5, sin cambio de lugar. Pero el 5 se compara con el 2, y se intercambian. El 5 queda ordenado. 0 1 2 3 tercera pasada: ahora ya sólo queda una comparación, entre el 3 y el 2. En este 3 2 5 7 caso se intercambian y el arreglo queda ordenado. 0 1 2 3 2 3 5 7 ordenado 0 1 2 3 Puede verse que si el arreglo tiene n elementos, serán necesarias a lo sumo n-1 pasadas para terminar de ordenarlo en el peor caso, y que en cada pasada se hace Ing. Valerio Frittelli - 437 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento cada vez una comparación menos que en la anterior. Otro hecho notable es que el arreglo podría quedar ordenado antes de la última pasada. Por ejemplo, si el arreglo original hubiese sido [2 – 3 – 7 – 5], entonces en la primera pasada el 7 cambiaría con el 5 y dejaría al arreglo ordenado. Para detectar ese tipo de situaciones, en el algoritmo se agrega una variable a modo de bandera de corte: si se detecta que en una pasada no hubo ningún intercambio, el ciclo que controla la cantidad de pasadas se interrumpe antes de llegar a la pasada n-1 y el ordenamiento se da por concluido. Se ha denominado ordenamiento de burbuja porque los elementos parecen burbujear en el arreglo a medida que se ordena... ()… La siguiente función del módulo ordenamiento.py (proyecto [F22] Ordenamiento) lo implementa: def bubble_sort(v): n = len(v) for i in range(n-1): ordenado = True for j in range(n-i-1): if v[j] > v[j+1]: ordenado = False v[j], v[j+1] = v[j+1], v[j] if ordenado: break b.) Ordenamiento por Inserción Directa (o Inserción Simple): La idea es ahora distinta y más original. Se comienza suponiendo que el valor en la casilla v conforma un subconjunto. Y como tiene un solo elemento, está ordenado. A ese subconjunto lo llamamos un grupo ordenado dentro del arreglo. Se toma v y se trata de insertar su valor en el grupo ordenado. Si es menor que v se intercambian, y si no, se dejan como estaban. En ambos casos, el grupo tiene ahora dos elementos y sigue ordenado. Se toma v y se procede igual, comenzando la comparación contra v (que es el mayor del grupo). Así, también hacen falta n-1 pasadas, de forma que en cada pasada se inserta un nuevo valor al grupo. El algoritmo procede como se muestra en la Figura 3: Figura 3: Funcionamiento general del Algoritmo de Ordenamiento por Inserción Directa. primera pasada: El grupo ordenado contiene sólo a v (con valor 7). Se inserta el 3 en ese grupo. Como el 3 es menor al 7, se intercambian y el grupo pasa a tener 7 3 5 2 ahora dos elementos, ordenados. 0 1 2 3 segunda pasada: Se inserta el 5 en el grupo. Se compara primero con el 7, y como el 5 es menor, se intercambian. Luego el 5 se compara con el 3, sin cambios. El grupo 3 7 5 2 tiene ahora 3 elementos, ordenados. 0 1 2 3 tercera pasada: Se inserta el 2. Primero se compara contra el 7 y se intercambian. 3 5 7 2 Luego el se compara contra el 5 y también cambian. Y finalmente se compara con el tres, y vuelven a intercambiarse. El arreglo queda ordenado. 0 1 2 3 2 3 5 7 ordenado 0 1 2 3 Ing. Valerio Frittelli - 438 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento La función que sigue (ver módulo ordenamiento.py del proyecto [F22] Ordenamiento) lo implementa: def insertion_sort(v): n = len(v) for j in range(1, n): y = v[j] k = j - 1 while k >= 0 and y < v[k]: v[k+1] = v[k] k -= 1 v[k+1] = y 3.] Algoritmos de Ordenamiento Compuestos o Mejorados: El Algoritmo Shellsort. Como dijimos, los algoritmos designados como Compuestos o Mejorados están basados en la idea de mejorar algunos aspectos que hacen que los algoritmos directos no tengan buen rendimiento cuando el tamaño del arreglo es grande o muy grande. De los tres algoritmos que hemos mencionado en la tabla de la Figura 1 (Quicksort, Heapsort y Shellsort), analizaremos en esta sección sólo el mecanismo de funcionamiento de trabajo del Shellsort, que es el más simple en cuanto a su estructura y fundamentos. El algoritmo Quicksort aplica una estrategia recursiva conocida como Divide y Vencerás y será analizado con detalle cuando se exponga esa estrategia en una Ficha posterior. Finalmente, el algoritmo Heapsort se basa en el uso de una estructura de datos conocida como Heap (o Grupo de Ordenamiento) que escapa a los contenidos mínimos de este curso. No obstante, por si algún estudiante siente curiosidad por la forma general de funcionamiento de este algoritmo, lo hemos incluido en esta Ficha en forma de tema totalmente opcional (no será evaluado ni exigido en ninguna de las evaluaciones de ningún tipo previstas para esta asignatura, aunque alguna pregunta podría surgir en el Cuestionario asociado a esta Ficha). De nuevo, suponemos en todos los casos un arreglo v de n elementos, y ordenamiento de menor a mayor. a.) Ordenamiento de Shell (Shellsort u Ordenamiento por Incrementos Decrecientes): El algoritmo de ordenamiento por Inserción Directa es el más rápido de los métodos simples, pues aprovecha que un subconjunto del arreglo está ya ordenado y simplemente inserta nuevos valores en ese conjunto de forma que el subconjunto siga ordenado. El problema es que si llega a aparecer un elemento muy pequeño en el extremo derecho del arreglo, cuando el grupo ordenado de la izquierda ya contiene a casi todo el vector, la inserción de ese valor pequeño demorará demasiado, pues tendrá que compararse con casi todo el arreglo para llegar a su lugar final. En 1959 un técnico de la General Electric Company llamado Donald Shell, publicó un algoritmo que mejoraba al de inserción directa y lo llamó High-Speed Sorting Procedure, aunque en honor a su creador se lo terminó llamando Shellsort. La idea es lanzar un proceso de ordenamiento por inserción, pero en lugar de hacer que cada valor que entra al grupo se compare con su vecino inmediato a la izquierda, se comience haciendo primero un reacomodamiento de forma que cada elemento del arreglo se compare contra elementos ubicados más lejos, a distancias mayores que Ing. Valerio Frittelli - 439 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento uno, y se intercambien elementos a esas distancias. Luego, en pasadas sucesivas, las distancias de comparación se van acortando y repitiendo el proceso con elementos cada vez más cercanos unos a otros. De esta forma, se van armando grupos ordenados pero no a distancia uno, sino a distancia h tal que h > 1. Finalmente, se termina tomando una distancia de comparación igual a uno, y en ese momento el algoritmo se convierte lisa y llanamente en una Inserción Directa para terminar de ordenar el arreglo. Las distancias de comparación se denominan en general incrementos decrecientes, y de allí el nombre con que también se conoce al método. En la Figura 4 mostramos la idea con un pequeño arreglo, suponiendo incrementos decrecientes de la forma [5 – 3 – 1]. Figura 4: Esquema general de funcionamiento del Algoritmo Shellsort. Primera pasada: armar grupos ordenados a incremento h = 5 distancia h = 5. Por ejemplo, los valores ubicados en v, v y v formarán un grupo ordenado. El valor v (un 0) entra al grupo y se compara con v (un 9). Como el 0 es menor que el 9, se intercambian. Y ahora el 0 (en v) se compara 5 8 10 7 6 9 1 4 3 2 0 contra el 5 (en v) y también se intercambian. Con los otros subconjuntos marcados con 0 1 2 3 4 5 6 7 8 9 10 colores, pasará lo mismo. 0 1 4 3 2 5 8 10 7 6 9 0 1 2 3 4 5 6 7 8 9 10 Segunda pasada: armar grupos ordenados a incremento h = 3 distancia h = 3. Las líneas de colores muestran qué elementos formarán cada grupo a distancia h = 3. Los colores de los números dentro del arreglo, muestran a qué grupo pertenecía cada número en la pasada h = 5. 0 1 4 3 2 5 6 9 7 8 10 0 1 2 3 4 5 6 7 8 9 10 Tercera pasada: armar grupos ordenados a incremento h = 1 distancia h = 1 – Fase de Inserción Directa Cuando h vale 1, simplemente se aplica un algoritmo de inserción simple, que termina de ordenar el arreglo (pero lo hará mucho más rápido, pues hay poca probabilidad de encontrar elementos demasiado lejos de su lugar final) 0 1 2 3 4 5 6 7 8 9 10 Arreglo ordenado... 0 1 2 3 4 5 6 7 8 9 10 Ing. Valerio Frittelli - 440 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento No es simple elegir los valores de los incrementos decrecientes, y de esa elección depende muy fuertemente el rendimiento del algoritmo. En general, digamos que no es necesario que esos incrementos sean demasiados: suele bastar con una cantidad de distancias igual o menor al 10% del tamaño del arreglo, pero debe asegurarse siempre que la última sea igual uno, pues de lo contrario no hay garantía que el arreglo quede ordenado. Por otra parte, es de esperar que los valores elegidos como distancias de comparación no sean todos múltiplos entre ellos, pues si así fuera se estarían comparando siempre las mismas subsecuencias de elementos, sin mezclar nunca esas subsecuencias. Sin embargo, no es necesario que los valores de los incrementos decrecientes sean todos necesariamente primos. Es suficiente con garantizar valores que no sean todos múltiplos entre sí. La función que sigue implementa el algoritmo de Shell. Está incluida en el módulo ordenamiento.py del proyecto [F22] Ordenamiento. def shell_sort(v): n = len(v) h = 1 while h 0: for j in range(h, n): y = v[j] k = j - h while k >= 0 and y < v[k]: v[k+h] = v[k] k -= h v[k+h] = y h //= 3 b.) El Algoritmo Heapsort. El método de ordenamiento por Selección Directa realiza n-1 pasadas, y el objetivo de cada una es seleccionar el menor de los elementos que sigan sin ordenar en el arreglo y trasladarlo a la casilla designada como pivot. El problema es que la búsqueda del menor en cada pasada se basa en un proceso secuencial, y exige demasiadas comparaciones. En 1964, un estudiante de Ciencias de la Computación, llamado J. Williams, publicó una mejora para el algoritmo de Selección Directa en Communicatons of the ACM, y llamó al mismo Ordenamiento de Montículos o Heapsort (en realidad, debería traducirse como Ordenamiento de Grupos de Ordenamiento, pero queda redundante...) Ese algoritmo reduce de manera drástica el tiempo de búsqueda o selección del menor en cada pasada, usando una estructura de datos conocida como grupo de ordenamiento (que no es otra cosa que una cola de prioridades, pero optimizada en velocidad: los elementos se insertan rápidamente, ordenados de alguna forma, pero cuando se extrae alguno, se extrae el menor [o el mayor, según las necesidades]) Igual que antes, al seleccionar el menor (o el mayor) se lo lleva a su lugar final del arreglo. Luego se extrae el siguiente menor (o mayor), se lo reubica, y así se prosigue hasta terminar de ordenar. En esencia, un grupo de ordenamiento es un árbol binario casi completo (todos los nodos hasta el anteúltimo nivel tienen dos hijos, a excepción de los nodos más a la derecha en ese nivel que podrían no tener los dos hijos) en el cual el valor de cada nodo es mayor que el valor de sus dos hijos. La idea es comenzar con todos los Ing. Valerio Frittelli - 441 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento elementos del arreglo, y formar un árbol de este tipo, pero dentro del mismo arreglo (de otro modo, se usaría demasiado espacio adicional para ordenar...). Es simple implementar un árbol completo o casi completo en un arreglo: se ubica la raíz en el casillero v, y luego se hace que para nodo en el casillero v[i], su hijo izquierdo vaya en v[2*i + 1] y su hijo derecho v[2*i + 2]. Así, el algoritmo Heapsort primero lanza una fase de armado del grupo, en la cual los elementos del arreglo se reubican para simular el árbol. La Figura 5 muestra un esquema general del proceso de armado del grupo inicial para un pequeño arreglo de cuatro elementos. Figura 5: Funcionamiento general del Algoritmo Heapsort - Fase 1: Armado del Grupo Inicial. primera pasada: Se toma el valor en v, y se supone que es la raíz del grupo de ordenamiento. Luego se toma v, y se lo considera como hijo izquierdo de 3 7 5 8 v. Se pretende armar un grupo en el cual cada nodo sea mayor que sus dos hijos, por lo se intercambia el 7 con el 3 para que el 7 quede como raíz. Los 0 1 2 3 elementos en verde, pertenecen ya al grupo. 7 v 3 v segunda pasada: Se toma el valor en v, y se lo considera como hijo derecho de v, por lo que hasta aquí, el árbol va bien. Los elementos en verde, pertenecen 7 3 5 8 ya al grupo. 0 1 2 3 7 v v 3 5 v tercera pasada: Se toma el valor en v, y se lo considera como hijo izquierdo de v. Como 8 es mayor que 3, deben rotar entre ellos. Pero eso haría que el 8 7 3 5 8 quede como hijo izquierdo del 7, y deben rotar otra vez. En este momento, todos los elementos pertenecen ya al grupo. 0 1 2 3 8 v v 7 5 v 3 v 8 7 5 3 Grupo armado... 0 1 2 3 Ing. Valerio Frittelli - 442 Cátedra de AED [Ciclo 2024] Ficha 22: Ordenamiento Una vez armado el grupo inicial1, comienza la segunda fase del algoritmo: Se toma la raiz del árbol (que es el mayor del grupo), y se lleva al último casillero del arreglo (donde quedará ya ordenado). El valor que estaba en el último casillero se reinserta en el árbol (que ahora tiene un elemento menos), y se repite este mecanismo, llevando el nuevo mayor al anteúltimo casillero. Así se continúa, hasta que el árbol quede con sólo un elemento, que ya estará ordenado en su posición correcta del arreglo. Gráficamente, la segunda fase se desarrolla como se muestra en la Figura 6. Figura 6: Funcionamiento general del Algoritmo Heapsort - Fase 2: Ordenamiento Final. primer paso: Se toma la raíz del árbol, el 8, y se almacena su valor en v. Con el 3 que estaba en v y ahora se intercambió con la raíz, se arma otra vez el árbol, considerando ahora sólo los casilleros v, v y v. El 3 no puede v quedar como raíz: se intercambia con el 7, que es el mayor de sus hijos. Los 8