Самая длинная последовательность Collatz-Memoization-Python-Iterative vs Recursive

Question

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]))) 

Как я могу запомнить все номера, используемые в одном вызове? Например, когда я вызываю recur (13), он будет хранить только значение 13 в dict, но не значения 40,20,10,5 и т. Д., Которые используются в recur (13)

Кроме того, я не могу для создания рекурсивной функции, которую я могу подсчитать (добавив аргумент счетчика в функцию), но затем я не могу добавить значения в словаре.

Просьба предложить способ, чтобы максимально возможные значения сохранялись в памяти, а также функция была рекурсивной?

Answer 1

Это наиболее читаемый (а также вполне путинский) способ записи рекурсивной функции, о которой я могу думать; это в основном просто излагает правила для создания последовательности, как вы бы объяснить это кому-то:

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) 

count Инициализация кэш 1 позволит оптимизацию, но жертвуют прямой перевод правила формирования в коде:

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]