# Collatz Conjecture

According to Wikipedia

The Collatz conjecture is a conjecture in mathematics named after Lothar Collatz. It concerns a sequence defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term. Otherwise, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.

## Recursive Implementation

Mathematically, this problem is naturally recursive and this is one way you could implement it as such in Python.

``````def collatz(n, previous=None):
if previous is None:
previous = []
if n == 1:
return previous + [n]

next_number = n//2 if n % 2 == 0 else n*3 + 1
return collatz(next_number, previous+[n])

for n in range(1, 10):
print(collatz(n))
``````
``````[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
``````

## Curried Recursive Implementation

This shows an example of currying, where you take a function that takes multiple arguments, and break it up into two or more functions where each function acts on only one argument in isolation. In functional languages like F#, variadic functions (those that take multiple arguments) are automatically curried, but this is how we would go about doing it in Python.

What I like about this is that we no longer have to assign a default value to the `previous` parameter and check its value on each call to our recursive function (`if previous is None`) like in your previous recursive example.

``````def collatz(n):
def get(previous):
nonlocal n
if n == 1:
return previous + [n]
else:
previous += [n]
n = n//2 if n % 2 == 0 else n*3+1
return get(previous)
return get([])

for n in range(1, 10):
print(collatz(n))
``````
``````[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
``````

## Imperative Generator Implementation

Another way we can solve this problem is using Python generator functions. This example uses a while loop to evaluate new values.

``````from functools import partial

# this decorator will turn a generator function to one that returns a list
listify = partial(lambda generator: lambda arg: list(generator(arg)))
``````
``````@listify
def collatz(n):
while n != 1:
yield n
n = n//2 if n % 2 == 0 else n*3 + 1

yield n

if n == 1:
return

for n in range(1, 10):
print(collatz(n))
``````
``````[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
``````

## Recursive Generator Implementation

Finally, this solution (my favorite) uses lazy evaluation and recursion to `yield from` itself until the base condition is met, that `n == 1`.

``````@listify
def collatz(n):
yield n

if n == 1:
return

next_number = n//2 if n % 2 == 0 else n*3 + 1

yield from collatz(next_number)

for n in range(1, 10):
print(collatz(n))
``````
``````[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
``````