lista enlazada y funcion recursiva

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

Un ejemplo del concepto es sumar.

Si hay una función:

Código PHP:

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

Código PHP:

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

//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 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!)