Lección 37: Aplicando recursividad - Ejemplo 2

[Vlady_18]

Seguimos entonces con este tema que tantos dolores de cabeza le trae a muchos programadores novatos porque no lo comprenden. He intentado a como de lugar que les sea sencillo de comprender aunque luego la parte de aplicación les queda a ustedes con los ejercicios; será allí que terminarán de comprender realmente este tema.

En esta lección veremos un caso donde aplicamos recursión de la forma conceptualmente más correcta. No será la única, lo demás se irá viendo en la práctica a medida que avancemos con el curso, pero les marcará las pautas que ustedes deben seguir a la hora de intentar realizar una tarea por medio de la recursividad.

------------------------------------------------------------------------------------

Caso 2 Iterativamente:

Este es el caso más claro y más correcto para la aplicación de esta funcionalidad, o sea, modificar una lista existente para agregarle un nodo. La idea no es utilizar una función sino que usaremos un procedimiento y pasaremos el parámetro l por referencia. De este modo queda implícito que ese parámetro representa la salida del procedimiento y que lo que se quiere hacer es modificar lo que allí se ingresa como parámetro efectivo. O sea, ya no hay duda de si lo que queremos hacer es retornar una copia de la lista o modificar la propia lista. Aún así, aclarar con comentarios no está de más.
Veamos entonces la versión iterativa:

PROCEDURE AgregarNumeroLista(VAR l: IntegerList; n: INTEGER);
VAR
    iter: IntegerList;
BEGIN
    IF l=NIL THEN
        NEW(l);
        l^.numero:= n;
        l^.siguiente:= NIL;
    ELSE
        iter:= l;
        WHILE iter^.siguiente<>NIL DO
            iter:= iter^.siguiente;
        END;
        NEW(iter^.siguiente);
        iter:= iter^.siguiente;
        iter^.numero:= n;
        iter^.siguiente:= NIL;
    END;
END AgregarNumeroLista;

El único cambio aquí es que no retornamos nada, o sea, borramos la sentencia RETURN l porque ya no estamos usando una función, sino un procedimiento. Si la lista es vacía trabajamos sobre el mismo parámetro l que como es por referencia es como trabajar sobre la misma variable Lista. Creamos un nuevo lugar de memoria y listo, queda pronto.

Aquí sí, si modifico el valor de l estoy modificando el valor de Lista, o sea, si hago l:= l^.siguiente o l:= NIL o l:= AgunaCosa estoy modificando a la lista original.

De este modo, cuando la lista no es vacía el código queda igual. Aquí está más que claro por qué utilizamos un puntero auxiliar llamado iter, o sea, lo necesito porque constantemente cambia de valor. Como no puedo usar l lo uso a él.

Cualquier cambio que hagamos sobre esa lista se reflejará en Lista, así que mucho ojo con estas cosas.

---------------------------------------------

Caso 2 recursivamente:

La forma recursiva será más sencilla y sobretodo no usaremos ese método sucio de un puntero auxiliar:

PROCEDURE AgregarNumeroLista(VAR l: IntegerList; n: INTEGER);
BEGIN
    IF l=NIL THEN
        NEW(l);
        l^.numero:= n;
        l^.siguiente:= NIL;        
    ELSIF l^.siguiente= NIL THEN
        NEW(l^.siguiente);
        l^.siguiente^.numero:= n;
        l^.siguiente^.siguiente:= NIL;        
    ELSE
        AgregarNumeroLista(l^.siguiente,n);
    END;
END AgregarNumeroLista;

Los casos base siguen siendo los mismos porque el problema sigue siendo el mismo. Ver lo que pasa con los casos base no tiene sentido porque es igual a la versión iterativa. Lo interesante es ver un caso con recursividad, así que veamos el mismo que antes:

El llamado ahora es: AgregarNumeroLista(Lista,40).
Entonces en el primer llamado tenemos esto que Lista y l son una misma cosa.



Ahí ven como si l apuntara a Lista, sí, l guarda la dirección de Lista y opera a través de ella. Ustedes para no complicarse la cabeza piensen que Lista y l son una misma variable. Si no lo tienen claro repasen el pasaje de parámetros por referencia dado en el curso de Pascal.

Como no estamos en ninguno de los caso base se realiza entonces un nuevo llamado recursivo. Aquí no queda nada pendiente, solo hay que recordar esto:

• l apunta al nodo con el número 50.

El nuevo llamado recursivo se hace pasando como parámetro a l^.siguiente, o sea, lo que en la ilustración se ve como un punto negro en el nodo del 50, que en realidad es un puntero hacia el siguiente nodo.

Entonces, el l del segundo llamado y el puntero del primer nodo son una misma variable:



El l de este llamado apunta entonces al nodo con el número 20.
Como no es caso base entonces tenemos un nuevo llamado recursivo pasando como parámetro al puntero l^.siguiente, en este caso como l apunta al nodo del 20 el l^.siguiente apunta al nodo del 30.

Entonces el l del tercer llamado apuntará al mismo lugar que el puntero del nodo del 20, siendo los dos como una misma variable:



Llegamos entonces al tercer llamado el cual representa un caso base. Creamos el nuevo nodo con lo cual tenemos esto:



Entonces comienza la vuelta atrás porque no hay nuevo llamado recursivo. Como en ninguno de los llamados quedaban cosas pendientes simplemente esta regresión continúa hasta terminar, con lo cual la lista original quedó modificada.

Esto deben probarlo, deben releerlo, deben seguirlo ustedes a mano con sus propios ejemplos, deben usar el depurador y ver qué pasa, etc.
Ahora bien, este método de aplicar la recursión nos permite mejorar nuestro algoritmo y tomarnos entonces un solo caso base. De este modo tenemos esto:

• La lista es vacía.
• La lista tiene al menos un elemento.

De este modo, si la lista recibida como parámetro es vacía creamos un nuevo elemento y sino, avanzamos una posición:

PROCEDURE AgregarNumeroLista(VAR l: IntegerList; n: INTEGER);
BEGIN
    IF l=NIL THEN
        NEW(l);
        l^.numero:= n;
        l^.siguiente:= NIL;        
    ELSE
        AgregarNumeroLista(l^.siguiente,n);
    END;
END AgregarNumeroLista;

Este código es mucho más claro que los anteriores. Si la lista es vacía hago algo, sino tomo una lista más pequeña a partir de la siguiente posición. Así, voy recortando el problema en problemas más pequeños.
Ahora bien ¿por qué inicialmente me tomé dos casos bases si podía aplicar uno solo? Pues por lo siguiente:

La versión funcional (en la que usamos una función), en cada llamado recibe por copia el mismo valor que la variable pasada como parámetro. O sea, el l dentro de la función apunta al mismo lugar que la variable que se pasa como parámetro pero es independiente, o sea, si modificábamos l no modificábamos la variable parámetro.
Entonces, si tenemos una lista con un solo elemento:



En un primer llamado tendremos un l que recibe por copia el valor de Lista, o sea apuntará al mismo lugar que Lista pero no serán como una sola variable, o sea, l y Lista serán independientes.

Esto, como ya dije es tramposo porque si hago por ejemplo DISPOSE(l) estoy borrando ese registro de memoria y liberándolo por lo tanto Lista perdería su referencia. Sin embargo, si hago l:= algunaCosa no pasa nada, solo modifico a l. Esto no ocurre en el pasaje por referencia.



Esta situación representaba un caso base. Sin embargo, en esta nueva versión del algoritmo no lo es, así que tendríamos un nuevo llamado recursivo donde tendríamos un l que apuntaría a NIL.



Lo que pasa es que el nuevo l recibe una copia de la variable que se le pasa como parámetro, en este caso sería el puntero llamado siguiente del nodo que tiene al 40. Entonces l toma el valor NIL. Pero NIL no es un lugar de memoria, es un valor que dice “No estoy apuntando a nada”. De este modo, si creo un nuevo registro de memoria utilizando l tendría esto:



O sea, estamos creando un nuevo registro pero suelto, no está anexado a la lista y no tenemos como anexarlo. En la vuelta hacia atrás ese registro quedaría perdido y la lista original no se vería modificada. Por eso nosotros nos deteníamos un nodo antes del nodo vacío y utilizábamos directamente el puntero l^.siguiente para crear el nuevo nodo, para que quedara anexado a la lista.

Con el pasaje de parámetros por referencia eso no sería así, porque l y el puntero del registro anterior son uno mismo, o sea, es así:



O sea, el l apunta a NIL pero a través del puntero anterior. O sea, son uno mismo. Por lo tanto si creamos un nuevo registro utilizando l es como si estuviéramos utilizando ese puntero.

Así, de este modo podemos detenernos justo donde debemos y no estar pensando en detenernos una posición antes. Además el código queda muchísimo más corto y más claro.

La recursividad tiene eso, hace códigos claros. Sin embargo puede resultar complicada y además consume más recursos del sistema porque crea registros en el Stack. Siendo así, si la lista fuera excesivamente larga la recursión no serviría porque llenaríamos el Stack antes de poder llegar al último nodo de la misma.

Por esto, si se quiere eficiencia generalmente se evita la recursividad. Sin embargo, en algunos casos será imprescindible.
Está claro que uno puede pensar que tiene bien claro lo que es el pasaje de parámetros pero sin embargo aquí vemos una sutileza que demuestra que hay cosas que se escapan.

También vieron que en función de cómo se piense implementar la recursividad cambia la cantidad de casos bases que tenemos, incluso ellos en sí mismos podrían cambiar.

Otra cosa super importante es que con el Caso 2, sea iterativo o recursivo, hemos cambiado la firma de la función. Esto sí afecta a sus llamados ya que si un parámetro se pasa por copia nosotros podemos pasar un valor específico en el llamado. Por ejemplo, si tenemos este procedimiento:

PROCEDURE Proc(numero: INTEGER);

que recibe un entero como parámetro por copia (por valor), entonces podríamos hacer un llamado así:

Proc(10);

o así:

Proc(X);

donde X es una variable INTEGER.

Ahora bien, si cambiamos la firma anterior por esta

PROCEDURE Proc(VAR numero: INTEGER);

solo admitirá variables como parámetros efectivos, no valores explícitos. O sea, el llamado

Proc(10);

ejará de ser válido pero

Proc(X);

seguirá funcionando.

Dado que nosotros pasábamos punteros como parámetros, es raro pasar una dirección de memoria como valor explícito, pero se puede hacer. De este modo, esto es algo a tener en cuenta porque puede afectar al resto del programa.

Seguiremos adelante con algún otro ejemplo antes de dar por terminado este tema.

Ojalá lo vallan llevando bien.

Ejercicio:

PROCEDURE P( x: CARDINAL );
BEGIN
    IF x=0 THEN
        WriteCard(x,1);
    ELSE
        WriteCard(x,1);
        P(x-1);
        WriteInt((-1)*x,1);
    END; 
END P;

ado el código del procedimiento P anterior ¿Qué salida produce en pantalla el llamado P(3)?

-------------------------------------------------------------

Un ejemplo matemático:

El factorial de un número natural es el producto (multiplicación) de ese número por todos sus anteriores. Ejemplos:

• El factorial de 5 es: 5*4*3*2*1.
• El factorial de 7 es: 7*6*5*4*3*2*1.
• El factorial de 4 es: 4*3*2*1.

La notación matemática para factorial es el símbolo !. Así, para denotar el factorial de 5 se escribe 5!, el factorial de 6 se escribe 6!. Entonces:

• 5!= 5*4*3*2*1.
• 7!= 7*6*5*4*3*2*1.
• 4!= 4*3*2*1.

El factorial de 1 claramente vale 1. El factorial de 0 se define matemáticamente como 1, o sea que:

• 0!= 1 por definición.

Entonces, dado un número, por ejemplo el 4, tenemos que 4!= 4*3*2*1. Pero sabemos que 3*2*1 equivale a 3!. Entonces podemos decir que:

• 4!= 4*3!
• 7!= 7*6!
• 100!= 100*99!
• n!= n*(n-1)!

Es decir, dado un número n, su factorial es ese número multiplicado por el factorial de su anterior.
Definiremos entonces, basados en lo que acabo de explicar, una función recursiva que calcula el factorial de un número natural dado.
Lo primero que hacemos es definirnos el caso base. Pues tomaremos que 0 es nuestro caso base ya que su factorial es 1 por definición, es decir, se resuelve por sí mismo. Para cualquier otro número diremos que su factorial es ese número por el factorial de su anterior. Fíjense, que si tenemos que calcualr el factorial de 1 podemos decir esto:

• 1!= 1*0!

y el resultado será correcto.

PROCEDURE Factorial(n: CARDINAL): CARDINAL;
BEGIN
    IF n=0 THEN
        RETURN 1;
    ELSE
        RETURN n*Factorial(n-1);
    END;
END Factorial;

Bien, aquí ven por primera vez un llamado recursivo que está dentro de una expresión, o sea, no es el llamado solo como teníamos antes, es decir, no es

RETURN Factorial(n-1)

sino que está dentro de una expresión.
En este ejemplo también vemos como sí utilizar el retorno del llamado recursivo, a diferencia del ejemplo anterior donde capturábamos ese retorno en una variable auxiliar y lo despreciábamos.
Hagamos entonces un seguimiento de esta función para un llamado con n=3. Entonces tenemos este llamado:

Factorial(3);

Entramos en la función con n=3, como no es el caso base pasamos a esta línea:

RETURN n*Factorial(n-1);

la cual equivale a

RETURN 3*Factorial(2);

Entonces, como hay un llamado recursivo, se genera un registro que recuerda:

• n= 3.
• Retornar el valor de n multiplicado por lo que de el factorial de 2.

Entramos entonces al factorial de 2. Ahora n vale 2, como no es caso base vamos al llamado recursivo:

RETURN n*Factorial(n-1)

que equivale a RETURN 2*Factorial(1).
Se genera este registro:

• n= 2.
• Retornar el valor de n multiplicado por el factorial de 1.

Así entramos al factorial de 1. Como no es caso base, vamos al nuevo llamado recursivo que en este caso es:

RETURN 1*Factorial(0);

Tenemos así:

• n= 1.
• Retornar el valor de n multiplicado por el factorial de 0.

Entonces entramos al factorial de 0. Como es caso base retornamos el valor 1. Dado que no hay más llamados recursivos, comienza la vuelta atrás.
Volvemos entonces al factorial de 1. Teníamos pendiente retornar el valor de n por el factorial de 0. Como el factorial de 0 tenemos que se retorna:

n*Factorial(0) = 1*Factorial(0) = 1*1 = 1, entonces retornamos 1.

Volvemos así al factorial de 2. Teníamos pendiente retornar el valor de n por el factorial de 1. Como n valía 2 teníamos:

n*Factorial(1) = 2*Factorial(1) = 2*1 = 2, entonces retornamos 2.

Volvemos a estar en el factorial de 3, donde teníamos pendiente retornar el valor de n por el factorial de 2:

n*Factorial(2) = 3*Factorial(2) = 3*2 = 6, entonces retornamos 6.

Como Factorial(3) fue el llamado inicial, no hay más nada por hacer. Obtuvimos así el valor 6, el cual es correcto, ya que:

3!= 3*2*1 = 6.



En esa ilustración he puesto todos los llamados de este ejemplo, utilizando colores distintos para cada uno para que vean como se concatenan. Léanlo en bajada (ida) y luego hagan la regresión.
Prueben ustedes mismos esa función en su XDS. Podrán calcular hasta el factorial de 12. Si utilizan otro número que sea mayor a 12 su programa caerá con el error:

#RTS: unhandled exception #5: whole overflow

¿Qué es eso? Pues WHOLE OVERFLOW significa: Desbordamiento de entero. Básicamente lo que está diciendo es que queremos representar un entero mayor a lo que soporta el lenguaje. Nos estamos yendo del tope. No olviden que los lenguajes tienen un número máximo y un número mínimo que pueden representar, si nos pasamos de eso el programa cae. Es una limitante del lenguaje. Una forma de hacer que esto no pase es colocar un IF que corrobore que n sea menor o igual que 12, y solo en ese caso calcule el factorial, o retorne 0.

Si cambian de compilador puede que ese valor sea mayor que 12, prueben ustedes hasta donde les permite llegar.

Versión iterativa de esta función:

PROCEDURE Factorial(n : CARDINAL) : CARDINAL
VAR 
    i, f : CARDINAL;
BEGIN
    f := 1;
    FOR i := 2 TO n DO
        f := f * i;
    END; (*for*)
    RETURN f;
END Factorial;

Conclusiones:

• La versión recursiva es más simple e igual a la definición matemática.
• La versión iterativa es más eficiente porque no usa la pila de memoria.

------------------------------------------------------------------------------

En la próxima lección les dejaré los ejercicios. Por ahora tienen bastante que hacer.

Saludos.

[LUK1LL45]

Impecable al igual que las demás lecciones.
Saludos.

[Vlady_18]

Gracias amigo.