Funciones recursivas en las hojas de cálculo

Cuando yo programaba hace años en Pascal se nos vendía su posibilidad de usar la recursión, es decir, que una función se llamara a sí misma, en declaraciones del tipo

Factorial(n)=n*factorial(n-1)

Esta y otras características nos hicieron abandonar el Basic como un lenguaje más primitivo y que no admitía funciones recursivas ni por asomo. Pasados bastantes años dejé la confección de programas ejecutables y consiguientemente el Pascal. Ahora que mis trabajos, por voluntad propia, los restrinjo a las hojas de cálculo y a su Basic, no uso la recursión…hasta hoy.

Preparando una próxima entrada se me ocurrió usar funciones recursivas en Excel, OpenOffice y LibreOffice (en Google Docs no funcionan las macros en Basic) con la sorpresa de que sí funcionaban bastante bien.

Toda función recursiva contiene una llamada a sí misma, directa o indirectamente a través de otra función. Como esto nos puede llevar a un proceso sin fin, debe contener también un código de parada, que suele ser una definición en un caso concreto, como veremos en los ejemplos.

La recursividad no se resuelve hasta que no desemboca en ese caso de parada. Mientras tanto hay que guardar los datos pendientes situándolos en una pila. Por tanto, ahí está el único problema de usar la recursividad en las hojas, y es que se puede agotar la pila si se alargan mucho los cálculos, con el consiguiente mensaje de error. Un fallo de principiante es programar una función recursiva sin facilitar su salida. En ese caso el error será más grave aún: un cálculo sin fin.

Explicamos a continuación algunas funciones recursivas, comenzando con el factorial, que es la más popular y que nos servirá para explicar algunos detalles:

Public Function factorial(n)
Dim f
If n = 0 Then f = 1 Else f = factorial(n - 1) * n
factorial = f
End Function

Es fácil entender  el código: Para evitar confusiones, comenzamos almacenando el factorial en la variable f, para al final recoger su valor en factorial. El cálculo de f es el clásico de la función n!: si n es cero, definimos el factorial como 1 y en caso contrario multiplicamos por n el factorial de n-1.

Prueba esta función en cualquiera de las tres hojas propuestas más arriba.

Este primer ejemplo contiene las dos partes imprescindibles en una función de este tipo:

- Alguna asignación de un valor concreto, que servirá para detener la primera fase de lectura de datos y comenzar los cálculos hacia atrás. Aquí es la asignación 0!=1

- La definición recursiva propiamente dicha, que, como es conocido, consiste en exigir que n!=n*(n-1)!

Lo explicamos con un esquema:

Al intentar calcular el factorial de 7, el programa se encuentra con una referencia al factorial de 6, guarda el 7 en la pila y se dedica a calcular el nuevo factorial. Como no puede, almacena el 6 encima del 7 (es una pila) y lo intenta con el 5, y así va de fracaso en fracaso (flecha descendente) hasta llegar al 0.

El valor 0 admite el cálculo, porque está definido como 1. Resuelto esto, es como si el programa se preguntara: ¿por dónde iba? Acude a la pila y ve un 1, con lo que ya puede calcular 1!=1*0!=1 y así sigue (flecha ascendente) buscando datos en la pila y resolviendo los cálculos según la definición recursiva.

Es evidente que para números grandes la pila se puede agotar por falta de memoria asignada.

Con esta función recursiva (la más inútil que me he inventado nunca) puedes tener una idea de la amplitud de la pila de tu hoja de cálculo.

Public Function identidad(n)
Dim i
If n = 1 Then i = 1 Else i = identidad(n - 1) + 1
identidad = i
End Function


La he elegido para que no influya la magnitud de los números, sino la cantidad de ellos que permanecen en la pila. Con ella he llegado la valor n=3270 como el último que no me da error. En los siguientes no consigo realizar el cálculo.

¿Qué margen tendrá tu hoja de cálculo? Prueba a ver.


Ejemplos varios

Si deseas el enésimo número triangular, sólo tienes que usar este código:

Public Function triang(a)
Dim p
If a = 1 Then p = 1 Else p = triang(a - 1) + a
triang = p
End Function

También se entiende bien: en los números triangulares vamos añadiendo en cada paso una base del triángulo nueva con a elementos. Prueba esta función y si quieres compara los resultados con la clásica fórmula T_n=n(n+1)/2.

¿Puedes analizar esta función?

Public Function cuad(a)
Dim p
If a = 1 Then p = 1 Else p = cuad(a - 1) + 2 * a - 1
cuad = p
End Function

¿Por qué produce como resultado el cuadrado de a? Este es un bonito ejemplo de elevar un número al cuadrado sin multiplicar en ningún momento.

Y ya que estamos con números poligonales, podríamos generarlos todos con una función recursiva única que dependiera de a y también del número de lados del polígono. ¿Te atreves con ella?

¿Y qué opinas de esta, con dos variables?¿Qué resultado produce?

Public Function combi(m, n)
Dim c
If n = 0 Then c = 1 Else c = combi(m, n - 1) * (m - n + 1) / n
combi = c
End Function

Ahora un ejemplo más serio:

En una entrada anterior (http://hojaynumeros.blogspot.com/2012/02/suma-de-los-elementos-de-todos-los.html) descubrimos que la suma de todos los elementos de los subconjuntos de un conjunto de n elementos venía dada por la fórmula de recurrencia

    S_n=2S_n-1+ n*2^n-1

y que da lugar a esta sucesión de valores en función de n

0, 1, 6, 24, 80, 240, 672, 1792, 4608, 11520, 28160, 67584, 159744, 372736, 860160, 1966080,…  (http://oeis.org/A001788)

Si definimos una función según esta recurrencia podremos reproducir esta lista en nuestra hoja de cálculo. Podría ser esta:

Public Function sumaelem(n)
Dim s
If n = 1 Then s = 1 Else s = 2 * sumaelem(n - 1) + n * 2 ^ (n - 1)
sumaelem = s
End Function

Con ella hemos construido esta tabla que coincide con la de OEIS

Un ejemplo elegante

Define esta función de texto

Public Function simetrico$(a$)
Dim s$
If a$ = "" Then s$ = "" Else s$ = simetrico(Right$(a$, Len(a$) - 1)) + Mid$(a$, 1, 1)
simetrico = s$
End Function

Escribe una palabra en una celda y aplícale esta función desde otra celda ¿Cuál es el resultado?

Como ves, todo esto es bastante divertido, pero no muy útil a causa del agotamiento del espacio de memoria asignado a la pila de datos.

Y ahora tú. ¿Cómo hallarías, mediante una función recursiva, el término general en estas sucesiones?

Progresiones aritméticas y geométricas.
La sucesión de Fibonacci (¡cómo no!)
La enésima potencia de un número dado.

Cribas y barridos 2. Otros ejemplos

Debemos insistir en esta segunda entrega del tema de barridos en que nuestro objetivo es la forma de presentar hechos y conceptos, y en ningún momento demostrar o comprobar.

Desarrollamos otros dos ejemplos:

Primos que se descomponen en suma de dos cuadrados

Sabemos que si un primo es de la forma 4k+1 se podrá descomponer en suma no trivial de dos cuadrados, siendo esto imposible si es de la forma 4k+3. Podríamos comprobar este hecho mediante un barrido.

Obtenemos una lista de primos y los acompañamos con un símbolo, y al lado su resto módulo 4.

Después engendramos todas las sumas de dos cuadrados en un rango adecuado, que puede ser la raíz cuadrada del último primo de la lista, o algo mayor por precaución ante redondeos. Para cada suma buscamos en la lista de primos si coincide con ella. En caso positivo borramos el símbolo, y quedarán como resultados negativos los que posean resto 3 respecto a 4.

Por si deseas profundizar, copiamos el código empleado en OpenOffice Calc, que puedes adaptar a tu caso cambiando la hoja, filas y columnas y también a Excel.

sub primos2cuad
dim i,j,k, rango
rango=15
for i=1 to rango
for j=1  to i
a=i^2+j^2
for k=1 to 50
if StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3,k).value=a then
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(4,k).string=" "
end if
next k
next j
next i
end sub

Conjetura de Goldbach

Cuando se conoce por primera vez la conjetura de Goldbach la idea inicial es la de ir seleccionando números pares para buscarles su descomposición de suma de dos primos. Podríamos cambiar la perspectiva: engendrar todas las sumas de dos primos en un rango y cotejar con una lista de números pares para ver si alguno de ellos es resultado de esa suma. En ese caso, como venimos haciendo, le borraríamos el símbolo que le acompañe.

Así que comenzamos con una lista de pares que comience en 4:

Después engendramos todas las sumas de dos primos impares con rango 200.  Para ello creamos la macro Goldbach, cuyo código se ofrece más abajo, y al ejecutarla, ¡zas!, todas las caritas desaparecen y queda comprobada la conjetura.

Código de la macro goldbach

sub goldbach
dim i,j,k, rango,p,q


rango=200
for i=3 to rango
if esprimo(i)=1 then
for j=1  to i
if esprimo(j)=1 then
a=i+j
p=int(a/40)
q=a-p*40
StarDesktop.CurrentComponent.sheets(2).GetCellByPosition(3+2*p,2+q/2).string=" "
end if
next j
end if
next i
end sub

Cribas y barridos 1. Números intocables

Dos características de la hoja de cálculo apreciamos mucho en este blog. Una es que permite estudios de nivel elemental y medio sin gran preparación previa en los trabajos y la otra su facilidad de presentación de estructuras y procesos matemáticos. Evidentemente, no  la recomendamos para estudios universitarios, aunque también podría dar juego, pero su uso del formato en coma flotante la imposibilita para el tratamiento exacto de grandes números.

Una posibilidad muy atractiva es la de presentar en pantalla resultados de cribas de números y barridos exhaustivos. Lo explicaremos con un ejemplo, el de los números intocables.

Se llaman así a aquellos números que no pueden ser el resultado de la suma de las partes alícuotas de otro número, es decir, de la suma de sus divisores propios. Por ejemplo, el 88 no coincide con ningún resultado de sumar los divisores propios de ningún otro número natural. Si efectuamos un barrido de los N primeros números y anotamos el resultado de esa suma, nunca resultará 88.

Los primeros números intocables son

2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248, 262, 268, 276, 288, …

http://oeis.org/A005114

Puedes aprender algo sobre estos números en la Red. Por ejemplo en http://mathworld.wolfram.com/UntouchableNumber.html, pero tampoco dan mucho de sí. Se aprenden sus propiedades en pocos minutos. Aquí nos va a interesar su generación y presentación atractiva con hoja de cálculo. Lo haremos con estos pasos:

(1) Presentemos los primeros números naturales en una pantalla de hoja de cálculo, y junto a cada uno escribamos cualquier símbolo, por ejemplo una carita sonriente:

La idea es que cuando encontremos un número que coincida con una suma de partes alícuotas de otro se borre la carita, y al final sólo la conserven los números intocables.

(2) Implementamos la función alícuota(n)

public function alicuota(n)
dim i,s
s=0
for i=1 to n/2
if n/i=n\i then s=s+i
next i
alicuota=s
End function

Esta función recorre los posibles divisores propios, con la prueba n/i=n\i, que equivale a afirmar que el cociente n/i es entero  que por tanto i divide a n. El resto se entiende fácilmente.

(3) Efectuamos un barrido de todos los posibles resultados de la función alícuota(n). Aquí hay un punto delicado y es el rango de cálculo que debemos elegir. Si deseamos encontrar los intocables menores que 100 deberemos buscar resultados hasta casi el 10000. El problema radica en que si un número es del tipo p+1 con p primo, será el resultado de la suma de divisores propios de p², como puedes razonar si te paras a pensar en ello. Como el máximo primo del 1 al 100 es 97, habrá que llegar más allá de 97²=9409.

La idea es que cada vez que salga una suma que equivalga a un número de nuestra tabla le borramos la carita sonriente, simplemente escribiendo sobre ella un espacio en blanco. Esto es muy dinámico, y si lo presentas a unos alumnos se darán cuenta de que sólo los números intocables se libran de que le borren la carita. Es una forma activa de comprender que estamos cribando números.

Para que todo funcione hay que encajar cada número en su fila y columna correspondiente para que localice la carita. Si cada columna contiene 20 números, hallaremos el cociente entero del resultado entre 20 y nos dará la columna y el resto resultante, la fila.

Lo puedes ver en este código (comentarios en cursiva):

sub intocables
dim i,f,c,p


for i=1 to 10000
p=alicuota(i) ‘ p es un resultado posible
if p<=100 then ‘restringimos p a la tabla que hayamos planteado
c=p\20  ‘se calcula la columna
f=p-20*c  ‘se calcula la fila
StarDesktop.CurrentComponent.sheets(3).GetCellByPosition(3+2*c,2+f).string=" "
‘se escribe un espacio en blanco en la celda. En el ejemplo se supone que trabajamos en la hoja 4 y que la tabla comienza en C3. Esta línea de código está adaptada a Calc. En Excel sería
ActiveWorkbook.Sheets(4).Cells(3+f,4+2*c).Value = " "
end if
next i
end sub

Al principio desaparecen las caras a gran velocidad, para ralentizarse después bastante. Las últimas en desaparecer son las de 80, 84 y 98 (¿por qué?). Al final queda así:

Quedan como supervivientes los números intocables.

¿Qué ocurriría si exigiéramos que no coincidieran con la suma de divisores propios, sino con la suma de todos (función SIGMA)? Nos daría una lista (más numerosa) de números intocables de otro tipo. Te dejamos el encargo.

¿En qué terminan los números triangulares?

Ideas para una webquest

“Los números triangulares, expresados en base decimal, no pueden terminar en 2, 4, 7 ó 9”

La metodología de las webquest se adapta muy bien al uso de las hojas de cálculo y a una buena atención a la diversidad. La afirmación anterior constituye un punto de partida que admite la organización de una webquest con distintos itinerarios de aprendizaje según los niveles del alumnado.
Se puede comenzar con la frase de arriba, y organizar una webquest para entender bien su significado y los fundamentos de esa afirmación. Incluimos a continuación algunos pasos que se podrían seguir:

(a) Definición de número triangular

Se puede buscar en páginas fiables, tales como Wikipedia o la misma Hojamat del autor de esta entrada.

(a1) Para el alumnado más aventajado, se sugerirá alguna búsqueda de carácter histórico sobre estos números.
(a2) Los estudiantes con dificultades pueden copiar imágenes de números triangulares y pegarlas en un documento.

(b) Fórmula de los números triangulares

Lo ideal sería que se pudiera deducir en el aula esta fórmua mediante inducción y discusión en grupos con la ayuda del profesorado. Así lo ha conseguido el autor en varias ocasiones, Si no, en las mismas páginas se puede encontrar dicha fórmula.

Una vez conseguida la fórmula T(n)=n(n+1)/2, se construye una tabla de números triangulares con una hoja de cálculo.

(b1) Este paso admite una rama de profundización consistente en buscar en la red propiedades de los números triangulares y experimentarlas con la misma hoja de cálculo. También se puede intentar generarlos por recurrencia: T(n+1) = T(n)+n+1
(b2) Una rama de consolidación del aprendizaje consistiría en aplicar esa fórmula sin el uso del ordenador y reproducir en papel las operaciones que se han efectuado en la hoja de cálculo.

(c) Terminación de los números triangulares

Ya se está en condiciones de comprobar que ningún número triangular termina en 2, 4, 7 ó 9, y, lo más importante, intentar justificarlo mediante la fórmula o razonamiento. Mediante la fórmula T(n)=n(n+1)/2 se puede discutir en qué cifra puede terminar n, después n+1, su producto y, por último, la mitad del mismo. Una tabla de hoja de cálculo podría ser muy útil.

(c1) Una actividad de perfeccionamiento consistiría en usar la propiedad de que “si tomo ocho veces un número triangular y después sumo 1, resulta un cuadrado”. Se estudian las terminaciones de los cuadrados impares, se les quita una unidad y se discute su cociente entre 8.
(c2) Para el alumnado que necesite consolidar lo aprendido, se puede organizar el cálculo de números triangulares grandes para comprobar sus terminaciones.

(d) Presentación de resultados

Todo el trabajo realizado se expone al resto del aula mediante documentos, presentaciones o puestas en común. Si se dispone de una web de centro, se incluye en ella todo el material generado en la webquest.

Con estas ideas, adaptándolas al nivel y características de vuestros estudiantes, podéis diseñar una o dos sesiones de trabajo que pueden resultar interesantes.