lista enlazada y funcion recursiva

[franco_cvm]

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:

type
pnodo=^tnodo;
tnodo=record
data: string;
prox: pnodo;
end;
var
p: pnodo;


function cantidad(p: pnodo):integer;
if P^.prox=nil then
cantidad=o
else
cantidad:=cantidad(p^.prox)+1;(

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?

[escafandra]

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.

[franco_cvm]

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).
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.

gracias igualmente

[mamcx]

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_(higher-order_function)

Un ejemplo del concepto es sumar.

Si hay una función:


function sum(list of numbers):number

result = sum([1, 2, 3])



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):


result = reduce(operator.add, [1, 2], 0)
//=3


Si a la gente le entran con esto, quedarian como "What????", porque, como rayos hace la suma?

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.com/questions/182314/recursion-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:


//Inicia. @ Indica que se guarda quien me esta llamando
stack.0 = []
stack.1 =[@sum, 1]
stack.2 =[@sum, @sum 1, 2]
stack.3 =[@sum, @sum 1, @sum 2]
//Cuando se retorna
result =[3]


Es por eso que puede haber un overflow: Los lenguajes normalmente tienen un area limitada (= tienen un tamaño maximo) para almacenar en el stack, y se supone (en los lenguajes imperativos) que la recursion es un caso aislado.

Por lo tanto, el stack (https://en.wikipedia.org/wiki/Stack_(abstract_data_type)#Stacks_and_programming_languages) 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!)

[escafandra]

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:


type
pnodo = ^tnodo;
tnodo=record
data: string;
prox: pnodo;
end;

var
p1, p2, p3, p4: tnodo;

function cuenta(nodo: pnodo): integer;
begin
Result:= 1;
if nodo <> nil then
Result:= Result + cuenta(nodo.prox);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
Count: integer;
begin
// no inicializo el string porque no es necesario para el ejemplo...
p1.prox:= @p2;
p2.prox:= @p3;
p3.prox:= nil;

Count:= cuenta(p1.prox);
end;


Saludos.