Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 61 vistas

    Reporte 3 Algoritmos

    Cargado por

    Dani Yagami
    El documento habla sobre algoritmos recursivos y estructuras de datos recursivas como pilas, listas y colas. Explica que un algoritmo recursivo resuelve un problema llamando a sí mismo con datos de tamaño menor, hasta alcanzar un caso base. También describe las pilas como estructuras LIFO y las listas como colecciones dinámicas construidas con nodos enlazados que almacenan un elemento y un puntero al siguiente nodo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Reporte 3 Algoritmos

    Cargado por

    Dani Yagami
    61 vistas5 páginas
    El documento habla sobre algoritmos recursivos y estructuras de datos recursivas como pilas, listas y colas. Explica que un algoritmo recursivo resuelve un problema llamando a sí mismo con datos de tamaño menor, hasta alcanzar un caso base. También describe las pilas como estructuras LIFO y las listas como colecciones dinámicas construidas con nodos enlazados que almacenan un elemento y un puntero al siguiente nodo.

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento habla sobre algoritmos recursivos y estructuras de datos recursivas como pilas, listas y colas. Explica que un algoritmo recursivo resuelve un problema llamando a sí mismo con datos de tamaño menor, hasta alcanzar un caso base. También describe las pilas como estructuras LIFO y las listas como colecciones dinámicas construidas con nodos enlazados que almacenan un elemento y un puntero al siguiente nodo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    61 vistas5 páginas

    Reporte 3 Algoritmos

    Cargado por

    Dani Yagami
    El documento habla sobre algoritmos recursivos y estructuras de datos recursivas como pilas, listas y colas. Explica que un algoritmo recursivo resuelve un problema llamando a sí mismo con datos de tamaño menor, hasta alcanzar un caso base. También describe las pilas como estructuras LIFO y las listas como colecciones dinámicas construidas con nodos enlazados que almacenan un elemento y un puntero al siguiente nodo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 5

    UNIVERSIDAD AUTONOMA DE NUEVOLEON

    FACULTAD DE INGENIERIA MECANICA Y

    ELECTRICA

    ALGORITMOS COMPUTACIONALES

    REPORTE #3

    Maestra: Ing. Jessica Natalia Martinez Balderas

    Alumno: Daniel Alejandro Martinez Martinez

    MATRICULA: 1919735 Carrera: ITS

    06/03/2021
    ALGORITMOS RECURSIVOS
    Un algoritmo recursivo es un algoritmo 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 subprograma se 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 esta forma, al ir reduciendo progresivamente la complejidad del
    problema que resolver, llegará un momento en que su resolución sea más o
    menos trivial (o, al menos, suficientemente manejable como para resolverlo de
    forma no recursiva). En esa situación diremos que estamos ante un caso base
    de la recursividad.

    Para implementar soluciones recursivas en un lenguaje de programación


    tenemos que utilizar una acción que se invoque a sí misma −con datos cada
    vez “más simples” −: funciones o procedimientos.
    ¾ Para entender la recursividad, a veces resulta útil considerar cómo se ejecuta
    las acciones recursivas en una computadora, como si se crearan múltiples
    copias del mismo código, operando sobre datos diferentes (en realidad sólo se
    copian las variables locales y los parámetros por valor).
    Pilas: Estructura de datos secuencial con acceso restringido.
    La principal característica de esta estructura es que el acceso tiene la propiedad
    “LIFO” (Last in, first out), cada vez que hacemos una llamada a a Cadena, incluimos
    un carácter en la pila.

    Ejemplo:

    Cola: a recursividad de “cola” es un mecanismo que permite tener funciones


    recursivas sin temer por posibles desbordamientos de pila. A diferencia de la
    recursividad normal, donde cada llamada recursiva implica la creación de un nuevo
    frame en la pila de llamadas (y por lo tanto el peligro de desbordar el tamaño de la
    pila), en la tail recursión es posible realizar dichas llamadas recursivas
    reaprovechando el frame de pila anterior y evitando así el desbordamiento.
    una ejecución normal, sin aplicar TCO, al principio en el frame global de pila
    tendríamos los valores de id y f (pues estas son las dos variables globales).
    Sabemos que cuando se llama a una función se crea un frame de pila que contiene
    los valores de las variables locales y la dirección de retorno. Así pues, cuando se
    llama a la función f dentro del console.log, se crea un frame en la pila de llamadas,
    con lo que ahora tenemos:

    Frame que contiene los valores locales de f (variables a y b) y la dirección de vuelta


    (línea C). Este es el top de la pila.
    Frame global
    Del mismo modo, cuando dentro de la función f se llama a la función id se crea un
    tercer frame en la pila de llamadas:

    Frame que contiene los valores locales de id (la variable x) y la dirección de vuelta
    (línea B). Este es el top de la pila.
    Frame que contiene los valores locales de f (variables a y b) y la dirección de vuelta
    (línea B).
    Listas: Listas: Las listas representan Colecciones de datos con ocupación en memoria
    dinámica. Se construyen en base a tipos recursivos. Útiles para el almacenamiento
    eficiente de datos. Tiene ventaja con respecto a la eficiencia en almacenamiento con
    respecto al vector, puesto que el tamaño de la lista (espacio en memoria) incrementa
    conforme se van añadiendo elementos a ella. Se encuentra en desventaja con
    respecto al tiempo de acceso con respecto al vector, puesto que requiere
    procesamiento para la localización, inserción, eliminación y determinar longitud de la
    lista, que se vuelve mayor conforme el tamaño de la lista crece. En contraste el vector
    provee acceso directo independientemente del tamaño del

    mismo, lo cual minimiza el procesamiento. Determinar la longitud de la lista puede


    optimizarse si la clase lista implementa un espacio reservado en memoria para la
    longitud, que va incrementando o decrementando según el tamaño de la lista cambia.
    Las listas hacen uso de un tipo recursivo conocido como “nodo”. Una lista es una
    composición de nodos, donde cada nodo está compuesto por el elemento que
    almacena y un apuntador que apunta al siguiente nodo de la lista. El último nodo de
    la lista apunta al apuntador nulo.

    Existen diversos tipos de listas enlazas. Cada tipo varía por la estructura de su tipo
    nodo. Los tipos de lista principales según sus nodos son:

    Lista simplemente enlazada con nodo cabecera: el tipo nodo de esta lista está
    compuesto por un registro con dos campos: “info” que representa el campo donde se
    almacena el elemento y “prox” que es un apuntador a nodo (apunta al siguiente
    nodo). Este tipo de lista contiene un nodo sin datos, que sirve como cabecera de la
    lista. El primer elemento de la lista inicia en el nodo número dos.

    Lista simplemente enlazada sin nodo cabecera: el tipo nodo de esta lista está
    compuesto por un registro con dos campos: “info” que representa el campo donde se
    almacena el elemento y “prox” que es un apuntador a nodo (apunta al siguiente
    nodo).
    El primer elemento de la lista se encuentra en el nodo número uno
    Lista doblemente enlazada con nodo cabecera: el tipo nodo de esta lista está
    compuesto por un registro con tres campos: “info” que representa el campo donde se
    almacena el elemento, “prox” que es un apuntador a nodo (apunta al siguiente nodo), y
    “ant” que es un apuntador a nodo (apunta al nodo anterior). Este tipo de lista contiene
    un nodo sin datos, que sirve como cabecera de la lista. El primer elemento de la lista
    inicia en el nodo número dos.

    Lista doblemente enlazada sin nodo cabecera: el tipo nodo de esta lista está
    compuesto por un registro con tres campos: “info” que representa el campo donde se
    almacena el elemento, “prox” que es un apuntador a nodo (apunta al siguiente nodo), y
    “ant” que es un apuntador a nodo (apunta al nodo anterior). El primer elemento de la
    lista se encuentra en el nodo número uno.

    Los tipos de lista principales según su semántica son:

    Lista básica: implementada con nodos del tipo “simplemente enlazados”. Permite
    almacenar datos con la semántica de un arreglo estático.

    Lista doble: implementada con nodos del tipo “doblemente enlazados”. Permite
    representar o emular carretes o cintas con principio y fin, permitiendo detenerse en un
    punto de la lista, avanzar o retroceder.

    Lista circular (ronda) básica: con nodos simplemente enlazados. Permite emular
    rondas o estructuras circulares. El último nodo de la lista apunta al primer nodo de la
    lista. Se recorre de izquierda a derecha.

    Lista circular (ronda) doble: con nodos doblemente enlazados. Permite emular rondas
    o estructuras circulares. El último nodo de la lista apunta al penúltimo y al primero. El
    primer nodo apunta al siguiente y al último. Se recorre de izquierda a derecha o de
    derecha a izquierda.

    EN CONCLUCION:
    Para finalizar me gustaría añadir que los algoritmos recursivos seme a echo
    un contenido muy interesante ya que abarca varios puntos que
    desconocía referente este campo, a sido de alto aprendizaje para mi este tema, espero
    y este estudio les parezca de alto agrado y cumpla con sus expectativas, lo hice lo
    mas completo posible y abarcando todos los puntos del tema , de
    mi parte seria todo gracias.
    Bibliografía
    • uv.mx. (15 de 04 de 2011). Obtenido de uv.mx:
    https://www.uv.mx/personal/ocastillo/files/2011/04/Recursividad.pdf
    • viva algoritmos y programacion. (16 de 07 de 2012). Obtenido de viva algoritmos y
    programacion: http://blogalgoritmosyprogramacion.blogspot.com/2012/07/tipos-recursivos-y-
    estructuras-enlazadas.html

    También podría gustarte