Переполнение стека рекурсии C++

Question

Я новичок в C++, но думал, что работа над некоторыми проблемами проекта Euler ознакомит меня с языком.

При попытке Project Euler Problem 14: Longest Collatz sequence

мне не удалось получить мои C++ решения работать, но не было никаких проблем с моим питоном решением ...

import time 
start = time.time() 
memo = {1:1,2:2} 
longest_chain, longest_starting_key = 2, 2 

def rec(a): 
    global longest_chain, longest_starting_key 

    if a in memo.keys(): 
     return memo[a]  
    if a % 2 == 0: 
     memo[a] = rec(a // 2) + 1 
    else: 
     memo[a] = rec(3 * a + 1) + 1 
    if memo[a] > longest_chain: 
     longest_chain = memo[a] 
     longest_starting_key = a 
    return memo[a]  

for i in range(1000000,3,-1): rec(i) 

print("starting key", longest_starting_key , ": has length", longest_chain) 
print((time.time() - start), "seconds") 

и получил

starting key 837799 has length 525 
1.399820327758789 seconds 

Моя попытка C++ ... (что я считал эквивалентной ...)

#include <iostream> 
#include <unordered_map> 
std::unordered_map<int, int> mem = { {1,1},{2,2} }; 
int longest_chain{ 2 }, best_starting_num{ 2 }; 

bool is_in(const int& i){ 
    auto search = mem.find(i); 
    if(search == mem.end()) 
     return false; 
    else 
     return true; 
} 

int f(int n){ 
    if(is_in(n)) 
     return mem[n]; 
    if(n % 2) 
     mem[n] = f(3 * n + 1) + 1; 
    else 
     mem[n] = f(n/2) + 1; 
    if(mem[n] > longest_chain) 
     longest_chain = mem[n]; 
    return mem[n]; 
} 

int main(){ 
    for(int i = 3; i < 1000000; i++){ 
     f(i); 
    } 
    std::cout << longest_chain << std::endl; 
} 

При запуске этого в Visual Studio в режиме отладки я получаю следующее сообщение об ошибке

Unhandled exception at 0x00007FF75A64EB70 in 
0014_longest)collatz_sequence_cpp.exe: 0xC00000FD: Stack overflow 
(parameters: 0x0000000000000001, 0x000000DC81493FE0). 

Кто-то сказал мне, что я должен выделить в куче с помощью указателей, но имеют очень ограниченный опыт работы с указателями .. .

Другая вещь, которую я не понимаю, - это когда я запускаю ее с 100'000 вместо 1'000'000 в петле основного тела, она работает, но очень медленная.

Answer 1

Подсказка: Что такое инвариант на интервале n, что последовательность Коллатца обеспечивает (математически), что ваш код Python удовлетворяет, но ваш код C++ не делает? Подсказка к подсказке: каковы последние несколько значений n перед переполнением стека?