FTP | CCD | Buscar | Trucos | Trabajo | Foros |
|
Registrarse | FAQ | Miembros | Calendario | Guía de estilo | Temas de Hoy |
|
Herramientas | Buscar en Tema | Desplegado |
#1
|
|||
|
|||
lista enlazada y funcion recursiva
Buenas, hace poco aprendí recursividad y lo había entendido( un caso base y después la función se llama a si misma acercándose mas al caso base) pero ahora con punteros y lista enlazada se me complica entender el codigo:
el código en cuestión, para saber la cantidad de nodos que tiene una lista:
he leído tutoriales de función recursiva pero no termino de entenderlo al máximo ¿mi duda es, como avanza mas allá de p^.prox para contar los otros nodos?¿como serian las registros de activación? |
#2
|
||||
|
||||
Para contar los elementos de una lista simplemente enlazada no necesitas una función recursiva, solo un bucle a través de los enlaces (punteros) hasta encontrar el valor nulo (el puntero del último elemento debe valer cero).
Saludos. |
#3
|
|||
|
|||
sisi, ya se, pero me piden que lo haga como función recursiva, y no logro entender el funcionamiento, es decir, que pasa cuando "lee" cantidad(p^.prox).
gracias igualmente |
#4
|
||||
|
||||
Lo que hace una funcion recursiva es una forma de un concepto mas general: Mapear y reducir, o mas concretamente, un FOLD:
https://en.wikipedia.org/wiki/Fold_(...order_function) Un ejemplo del concepto es sumar. Si hay una función: Código PHP:
dentro de sum debemos manejar el estado: Una vble empieza en cero (valor incial), mapeamos con un ciclo cada item de la lista, una vble acumula el resultado y una salida retorna el ultimo valor. Todo esto es muy obvio, y es lo que hace todo el mundo. El codigo es claro, porque la implementacion general es *explicita* y vemos el *manejo del estado* y el *proceso* tal cual. Ahora, un fold se escribe asi (python): Código PHP:
Y todo es porque fold es una de las "super-funciones" sobre la que se puede reconstruir casi de todo.. incluyendo la recursividad. Y porque abstrae el proceso! Y todo es porque un fold se encarga de mapear una lista, y acumula el resultado (ie: recuerda cual fue el resultado anterior) y se inicializa con un valor inicial, solo que es DECLARATIVO en vez de IMPERATIVO ---- Lo que le enrueda la pita a todo el mundo con la recursion es que existe un elemento "invisible" que es el que permite hacer todo eso. Es que los lenguages manejan internamente el stack! ---- Asi que en este caso, la parte "invisible" es la de recordar donde vamos. Eso es el stack: https://programmers.stackexchange.co...or-while-loops Por lo tanto, siguiendo con la idea, un lenguaje hace algo asi: https://www.youtube.com/watch?v=s8JpA5MjYac https://www.youtube.com/watch?v=ozmE8G6YKww Y en cada paso va acumulando el stack: Código PHP:
Por lo tanto, el stack es como la estructura de stack de cualquier lenguaje, solo que es *interna e invisible**y es como se hace pa recordar quien me llamo y con que parametros, es por eso que el stack se puede volver inmenso si la recursividad se vuelve grande. Un lenguaje funcional optimiza esto porque convierte las funciones compatibles con "TAIL RECURSION" de forma automatica a un ciclo imperativo, sacando el stack interno de la ecuacion. Otra forma es usar un estilo llamado "CONTINUATION PASSING STYLE" que en vez de guardar "quien me llamo, y todos los otros que han llamado a eso" solo guarda "a quien voy a llamar" y siempre en su stack solo habra 1 (= el stack nunca es mayor a 1!)
__________________
El malabarista. Última edición por mamcx fecha: 13-06-2015 a las 16:16:48. |
#5
|
||||
|
||||
Resumiendo y para que tengas una idea práctica de lo que te expone mamcx, te muestro como crear elementos de tu lista y como contarlos de forma recursiva, en lugar de con un simple bucle:
Saludos. |
|
|
Temas Similares | ||||
Tema | Autor | Foro | Respuestas | Último mensaje |
Duda lista enlazada | franco_cvm | Varios | 1 | 09-06-2015 21:58:59 |
Lista Enlazada | blackx5n | Varios | 3 | 03-04-2013 21:24:30 |
Como Invertir Una Lista Enlazada Simple | sant0s | OOP | 10 | 14-12-2011 20:55:24 |
Como hacer una lista enlazada dinamica en delphi | rgstuamigo | OOP | 40 | 04-12-2008 20:20:25 |
lo que necesito es ayuda en el TDA de una lista doblemente enlazada circular | program_tda | Varios | 12 | 17-02-2004 08:45:35 |
|