Trocitos de código (II). Recursividad y la función factorial

La función factorial aparece con mucha frecuencia en ejercicios de probabilidad, concretamente en los cálculos de combinatoria (combinaciones, variaciones y permutaciones). Esta función se puede definir de diferentes formas. Una de ellas, es la forma recursiva. Pero, ¿qué es la recursividad? El artículo explica el concepto de recursión o recurrencia, y como aplicarlo a funciones como el factorial de un número. Finalmente, se propone una implementación de la función con el lenguaje de programación Java.

Leí en el blog Fotomat sobre fotografía y matemáticas una fantástica frase para explicar la recursividad. También la fotografía que publica refleja perfectamente el concepto.

«Si un genio te ofrece tres deseos dile que te bastan dos: El 1º lo que quieras y el 2º otros dos deseos. Eso es recursividad

Una definición de recursividad (también llamada recursión o recurrencia) sería

«La recursividad es la forma en la cual se especifica un proceso basado en su propia definición.»

Como se puede observar en la imagen, en el cuadro que sostiene la chica, aparece de nuevo la imagen completa original. Y así sucesivamente, idealmente hasta el infinito. Sin embargo, cuando se utiliza la recursividad en matemáticas, es necesario definir lo que se denomina «caso base», una condición que permite evitar el carácter infinito de la recursividad.

Podemos encontrar muchos ejemplos de recursión en las funciones matemáticas. Uno de los ejemplos clásicos de funciones que pueden definirse de forma recursiva son la función factorial de un número: n!

¿Qué es el factorial de un número?

De nuevo, una definición:

Para todo entero positivo n, el factorial de n o n factorial se define como el producto de todos los números enteros positivos desde 1 (es decir, los números naturales) hasta n.

La letra pi mayúscula que aparece en la fórmula se llama productorio, y es un operador matemático (como el sumatorio) que representa una multiplicación de una serie de números (finita o infinita).

Es decir, para calcular por ejemplo el factorial de 6, y se expresa como 6!, habría que realizar el producto de los número naturales desde 1 (k=1) hasta 6 (que es el valor de n).

Se dice que este método para calcular la función factorial es de tipo iterativo. Se realiza un recorrido (iteración) por los distintos números, multiplicando en cada paso cada número de la serie por el siguiente (que es el anterior más 1).

Se trata de una función que aparece con mucha frecuencia en los cálculos de combinatoria (combinaciones, variaciones y permutaciones), fundamental para el cálculo de probabilidades. De hecho, en cualquier calculadora científica, podemos encontrar una tecla que realiza precisamente esta función sobre un número.

Pero también existe una definición recursiva de la función factorial.

Podemos observar que en la definición de la función factorial (la expresión a la derecha del símbolo «=»), aparece de nuevo la función factorial. Esta situación corresponde con la definición de recursividad que comentábamos al principio: «la forma en la cual se especifica un proceso basado en su propia definición.»

Ahora sabemos que la calculadoras disponen de la función factorial. Pero, ¿cómo se puede programar este cálculo con un ordenador? Los lenguajes de programación también permiten definir funciones de forma recursiva, y un ejemplo de implementación de la función factorial en Java sería la siguiente (clic sobre la imagen para probar el código).

El desarrollo de la función factorial de forma recursiva según el código anterior sería:

factorial(6) = 6·factorial(5)
factorial(5) = 5·factorial(4)
factorial(4) = 4·factorial(3)
factorial(3) = 3·factorial(2)
factorial(2) = 2·factorial(1)
factorial(1) = 1·factorial(0)
factorial(0) = 1

Y procediendo y resolviendo en orden inverso:

factorial(0) = 1
factorial(1) = 1·factorial(0) = 1
factorial(2) = 2·factorial(1) = 2·1 = 2
factorial(3) = 3·factorial(2) = 3·2 = 6
factorial(4) = 4·factorial(3) = 4·6 = 24
factorial(5) = 5·factorial(4) = 5·24 = 120
factorial(6) = 6·factorial(5) = 6·120 = 720

Este último paso se denomina caso base. En algún momento, la recursión debe terminar. Si ni impusiéramos una última condición, la recursión seguiría indefinidamente.

Código Java | Función factorial
En Tiching | Recursividad y la función factorial
Foto Recursividad | Fotomat
Foto Calculadora | por Simon Q en Flickr

Trocitos de código (I). Lanzando una moneda millones de veces: ¿cara o cruz?

Empieza en el blog la sección «Trocitos de código», una serie de artículos donde comparto ejemplos de programas escritos con algún lenguaje de programación y que resuelve algún problema concreto, especialmente de matemáticas. Esta semana, la simulación de millones de lanzamientos de una moneda.

Hace unos días explicaba cómo realizar una simulación del lanzamiento de un dado utilizando las funciones de generación de número aleatorios y de recuento de la hoja de cálculo. Los resultados del experimento permitían comprobar la Ley de los Grandes Números.

Diseñar la hoja de cálculo que simula el experimento no entraña demasiada dificultad, si uno sigue los pasos indicados en la actividad y ha utilizado fórmulas de hoja de cálculo en alguna ocasión (recomiendo echar un vistazo a las fichas sobre OpenOffice Calc que preparé hace tiempo). Sin embargo, el entorno de hoja de cálculo no siempre es el más adecuado para realizar algunos experimentos. Cualquiera que intente aumentar el número de lanzamientos de dado de la actividad, comprobará que la memoria del sistema se resiente, y es más que probable que el ordenador se «cuelgue» durante algunos segundos. Los programas de ofimática son lo que son; no les podemos pedir más.

En realidad es una excusa para introducir una nueva sección en el blog: «Trocitos de código», entradas en las que comparto algún fragmento de código (conocidos en inglés como, Code Snippets) escritos con algún lenguaje de programación y que resuelve algún problema concreto. No es mi intención (de momento) explicar ningún concepto de programación, pero si despertar la curiosidad por este arte y utilizarla como herramienta para poner a prueba y comprender mejor algunos conceptos matemáticos.

Lanzamiento de una moneda

En esta ocasión propongo la simulación del lanzamiento de una moneda para comprobar de nuevo la Ley de los Grandes Números:

«La frecuencia relativa de un suceso tiende a estabilizarse hacia una constante a medida que se repite el experimento.»

En el caso de una moneda, en cada lanzamiento la probabilidad de que salga «cara» o «cruz» es exactamente la misma (son sucesos equiprobables), de modo que para cada posible resultado la probabilidad es del 50% (0,5 para «cara» y 0,5 para «cruz»).

La probabilidad de un suceso es la constante a la que se aproxima la frecuencia relativa cuando el experimento se repite muchísimas veces.

Simulación con Java: versión «mini»

Sabemos que debemos repetir el experimento de lanzar la moneda un número «muy grande» de veces. El siguiente fragmento de código escrito en Java realiza precisamente el experimento de lanzar una moneda. Por defecto lo hace 10 millones de veces (l=10000000) y cada 5000 lanzamientos (m=5000) muestra la frecuencia relativa hasta el momento. Lógicamente, estos valores se pueden cambiar.

Para modificar el problema, bastaría con utilizar cualquier editor de «texto plano» para realizar los cambios. Y para generar el programa final y probarlo, habría que disponer de un entorno de compilación y ejecución de Java. Bien, nada de esto es necesario. Existen en Internet algunos entornos de compilación y ejecución online, que permiten probar fragmentos de código. Este es el caso de rextester, una página web en la que podemos escribir nuestro código en varios lenguajes de programación y probar su funcionamiento, además de guardarlo y compartirlo con otros usuarios.

He utilizado este entorno para que podáis probar fácilmente la versión «mini» del programa que realiza la simulación del experimento (clic sobre la imagen del código). Una vez en la web de rextester, basta con hacer clic sobre «Run it» o darle a la tecla F8.

Simulación con Java: versión completa

La versión anterior utiliza el código mínimo (o casi) para realizar la simulación. Este segundo ejemplo de código, mucho más completo y con comentarios, muestra la simulación paso a paso, con los detalles de los lanzamientos de moneda.

Una vez lanzada la simulación, observamos los resultados del experimento. En cada fila aparecen 10 lanzamientos de moneda, con una C o una X, según el resultado de «cara» o «cruz» obtenido. Cada 10 lanzamientos se calcula la frecuencia relativa del suceso «sacar cruz». En los primeros lanzamientos, observamos que el valor de frecuencia relativa ronda 0,5 pero es inestable.

Sin embargo, a medida que el número de lanzamientos crece considerablemente, comprobaremos que la frecuencia relativa se va estabilizando y aproximando de forma más exacta al valor 0,5.

Simulación con GeoGebra

Este mismo experimento se puede realizar también con GeoGebra, un software para matemáticas del que ya he hablado en Esfera TIC en más de una ocasión. La simulación del experimento de lanzar una moneda se puede repetir 10, 100 y 1000 veces.

En Tiching | Lanzando una moneda millones de veces
Código 1 | Lanzamiento de una moneda (versión mini)
Código 2 | Lanzamiento de una moneda (versión completa)
Simulación con GeoGebra | Lanzamiento de una moneda
Foto código | Ruby ruby de Elliott Cable en Flickr
Foto moneda | Lucky Six – PCA 58 de Donald Macleod