Conjetura de Collatz en Python. Recursivo vs iterativo

La conjetura de Collatz fue enunciada por el matemático Lothar Collatz en 1937 y todavía no ha sido demostrada. Esta conjetura dice que dado cualquier número entero positivo, aplicando estas dos reglas, acaba siendo siempre 1.

  • Si el número es par, se divide entre 2
  • Si el número es impar, se multiplica por 3 y se suma 1

Ejemplo partiendo de 6:

  • 6 es par, dividimos entre 2 = 3
  • 3 es impar, multiplicamos por 3 y sumamos 1 = 10
  • 10 es par, dividimos entre 2 = 5
  • 5 es impar, multiplicamos por 3 y sumamos 1 = 16
  • 16 es par, dividimos entre 2 = 8
  • 8 es par, dividimos entre 2 = 4
  • 4 es par, dividimos entre 2 = 2
  • 2 es par, dividimos entre 2 = 1

En la Wikipedia hay más información sobre la conjetura de Collatz.

Vamos a implementar un algoritmo con la conjetura de Collatz de dos formas distintas, una de forma recursiva y otra de forma iterativa.

Diferencias entre recursividad e iteración

La iteración consiste en repetir una y otra vez una o varias sentencias usando bucles for, while etc. La iteración es la más común a día de hoy, pero va perdiendo terreno a causa del auge de la programación funcional.

Hablamos de recursividad cuando una función se llama a sí misma una y otra vez. Es más elegante que la iterativa porque se usa menos código y es más fácil leerlo, aunque si no estamos acostumbrados, dificulta un poco la implementación de un método recursivo. Pero tenemos que tener en cuenta la siguiente frase:

Code is read many more times than written

El problema de la recursividad es que afecta al rendimiento, ya que al llamarse una función a sí misma, se mantienen los registros de las funciones en la memoria RAM y puede llegar a ocuparla por completo.

Algoritmo recursivo

Esta sería la implementación de la conjetura de Collatz de forma recursiva:

def calculaCollatz(pNumero):
    print('Numero actual: {0}'.format(pNumero))

    if pNumero != 1:
        if pNumero % 2 == 0:
            pNumero = pNumero // 2
        else:
            pNumero = pNumero * 3 + 1

        calculaCollatz(pNumero)

Algoritmo iterativo

Y esta de forma iterativa:

def calculaCollatzIterativo(pNumero):
    while pNumero > 1:
        print('Numero actual: {0}'.format(pNumero))

        if pNumero % 2 == 0:
            pNumero = pNumero // 2

        else:
            pNumero = pNumero * 3 + 1
    else:
        print('Numero actual: {0}'.format(pNumero))

Pruebas y resultados

Para hacer las pruebas con números muy muy grandes para que haya una diferencia real en los tiempos de cálculo he tenido que cambiar el nivel máximo de recursión de Python que por defecto es 999. Para cambiarlo, hacemos uso de la librería sys:

import sys
sys.setrecursionlimit(100000000)

Estos son los tiempos obtenidos tras varias ejecuciones:

Tiempo recursivo: 0.7219452857971191
Tiempo iterativo: 0.6483826637268066

Tiempo recursivo: 0.5863070487976074
Tiempo iterativo: 0.5835487842559814

Tiempo recursivo: 0.5863070487976074
Tiempo iterativo: 0.5835487842559814

Tiempo recursivo: 0.6134541034698486
Tiempo iterativo: 0.5413932800292969

Como vemos, la diferencia no es muy bestia, pero en un proceso de menos de un segundo ya es palpable. Para procesos muy costosos, la recursividad no es buena opción, ya que ocuparíamos toda la memoria y podríamos no obtener un resultado.

Publicado por Fj Asensi

BigData & MachineLearning Developer | Senior Microsoft Dynamics 365 Business Central Developer

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Salir /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Salir /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Salir /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Salir /  Cambiar )

Conectando a %s

A %d blogueros les gusta esto: