Pilas y recursividad

Instituto Politécnico Nacional Escuela Superio de Cómputo
PROGRAMACIÓN III Práctica 3: Pilas y recursividad
Alumnos:
Valle Vieyra Alvaro Emmanuel
Cerón Blanco Monserrat
2007630534
2007630069Resumen:
En esta práctica repasamos los conceptos de pilas y algoritmos recursivos.
Introducción
Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de accesoa sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido
asu simplicidad y ordenación implícita en la propia estructura.
Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), y retirar (o desapilar, pop) En cada momento sólo setiene acceso a la parte superior de la pila, es decir, al
último objeto apilado (denominado TOP). La operación retirar-pop permite la obtención de este elemento.
Un algoritmo recursivo es unalgoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.
Generalmente, si la primera llamada al subprogramase plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De estaforma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como pararesolverlo de forma no
recursiva). En esa situación diremos que estamos ante un caso base de la recursividad. Las claves para construir un subprograma recurrente son:
• Cada llamada recurrente se deberíadefinir sobre un problema de menor complejidad (algo más fácil de resolver).
• Ha de existir al menos un caso base para evitar que la recurrencia sea infinita. Es frecuente que los algoritmos...