CODEWITHSUNDEEP
python-3.xdynamic-programmingmemoization
Utkarsh Mittal
Utkarsh Mittal

Reputation: 141

Longest Collatz Sequence- Memoization- Python- Iterative vs Recursive

dict={}
def recur(n):
    counter=1
    original=n
    while n!=1:
        n = n/2 if n % 2 == 0 else 3*n+1
        if n in dict:
            counter=counter+dict[n]
            dict[original]=counter
            return counter

        counter=counter+1
    dict[original]=counter
    return counter
for i in range(1,1000000):
    recur(i)
print(max(dict.keys(), key=(lambda k: dict[k])))

How can I memoize all the numbers used in one calling? For example when I call recur(13), it will store only the value of 13 in dict but not the values of 40,20,10,5 etc that are used in recur(13)

Also, I am unable to produce a recursive function as I can either count (by adding counter argument in function) but then I can't add the values in dictionary.

Please suggest a way so that maximum possible values are stored in memory and also the function is recursive?

Upvotes: 2

Views: 738

Answers (1)

Thomas Lotze
Thomas Lotze

Reputation: 5323

This is the most readable (and also quite pythonic) way to write the recursive function that I can think of; it basically just spells out the rule for building the sequence as you'd explain it to somebody:

count = {}

def recur(n):
    if n not in count:  # memoize
        if n == 1:
            count[n] = 0  # finished
        else:
            count[n] = recur(n//2 if n % 2 == 0 else 3*n + 1)
        count[n] += 1  # this step
    return count[n]

for i in range(1, 100):
    recur(i)

for item in sorted(count.items()):
    print(item)

Initialising the count cache with 1 will allow an optimisation but sacrifice the direct translation of the formation rule into code:

count = {1: 1}

def recur(n):
    if n not in count:  # memoize
        count[n] = 1 + recur(n//2 if n % 2 == 0 else 3*n + 1)
    return count[n]

Upvotes: 1

Related Questions