Applying memoization makes golom sequence slower

On top of the other answers, I would like to add that this could really benefit from proper benchmarking.

In order to get reliable results you want to run the tests multiple times, and take steps to ensure that memory caches and other system-level shenanigans aren't interfering with the results.

Thankfully, there are libraries out there that can handle most of these complexities for us. For example, here's a better benchmark of your code using google's Benchmark library:

N.B. the fixes proposed by the other answers have been integrated.

#include <chrono>

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1 + golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int>& golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}


static void TestGolomb(benchmark::State& state) {
  for (auto _ : state) {
    benchmark::DoNotOptimize(golom(state.range(0)));
  }
}
BENCHMARK(TestGolomb)->DenseRange(1, 17, 2);

static void TestGolombS(benchmark::State& state) {
  for (auto _ : state) {
    // Make sure we always start from a fresh map
    std::unordered_map<int, int> golomb;

    // Ignore construction and destruction of the map
    auto start = std::chrono::high_resolution_clock::now();
    benchmark::DoNotOptimize(golomS(state.range(0), golomb));
    auto end = std::chrono::high_resolution_clock::now();

    auto elapsed_seconds =
      std::chrono::duration_cast<std::chrono::duration<double>>(
        end - start);

    state.SetIterationTime(elapsed_seconds.count());
  }
}
BENCHMARK(TestGolombS)->DenseRange(1, 17, 2);

Which gives us the following profile suggesting that the breakeven point is around 14-15:

see on quick-bench

int golomS(int n, std::unordered_map<int, int> golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

In your goloms function, you pass golomb as a value, not a reference. That means that every time you call goloms, the compiler will make a copy of golomb and destroy that copy when it's out of scope, not changing the actual golomb value.

You should pass by reference instead.

int golomS(int n, std::unordered_map<int, int>& golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

There are two issues in your code. First main issue is that you pass unordered map by value. You have to pass it by reference to make it faster, to avoid copying whole map on every function call. Also if you pass map by value then on return newly computed values are not preserved, but if you pass it by reference then new values will give benefit to caller functions.

Second important issue is that you use very small value 4 as input of a function to measure time, it takes very little time for 4 to compute, you have to use bigger value like 50, so that it takes more time to compute and hence gives more accurate time measurement.

Fixed version of your code has already very improved timings of first function compared to second (for input 50):

13
13
Time taken by function 1: 110 microseconds
Time taken by function 2: 118345 microseconds

Fixed code:

Try it online!

#include <unordered_map>
#include <iostream>
#include <chrono>

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1 + golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int> & golomb)
{
    if(n == 1)
        return 1; 
    if(golomb.find(n) == golomb.end())
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    return golomb[n];
}

int main(int argc, char* argv[])
{
    std::unordered_map<int, int> hashTable;
    
    auto start = std::chrono::high_resolution_clock::now(); 
    std::cout << golomS(50, hashTable) << std::endl;
    auto stop = std::chrono::high_resolution_clock::now();
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::cout << golom(50) << std::endl;;
    auto stop1 = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(stop1 - start1);

    std::cout << "Time taken by function 1: "
           << duration.count() << " microseconds" << std::endl;
    
    std::cout << "Time taken by function 2: "
          << duration1.count() << " microseconds" << std::endl;
    
    return 0;
}

Very good. Please try and continue to learn about memoization.

I will give an additional method. You can also "memoize" values in a DP table. DP like dynamic programming.

If you go for speed and can afford a big memory consumption, then this is the fastest and most efficient solution. Using recursion for that sequence is basically a bad idea and will result in very slow code and potential stack overflows.

Converting the recursive into an iterative solution with memoization in a DP table, will give you a very fast result. Even for big numbers. With compiler optimizations on, you can calculate the complete sequence for example up to 100000 ultrafast.

See the below:

#include <iostream>
#include <array>
#include <cstdint>

// We will calculate a Golomb sequence up to the below specified element
constexpr size_t MaxValues = 100000;

using MyDataType = uint_fast16_t;
using GolombSequence = std::array<MyDataType, MaxValues>;

// This is the Golomb Sequence
GolombSequence golombSequence{};

// Iterative Function to calculate a Golomb sequence using a DP table
void createGolombSequence() {

    golombSequence[1] = 1;
    for (int i = 2; i < MaxValues; ++i) {
        golombSequence[i] = 1 + golombSequence[i - golombSequence[golombSequence[i - 1]]];
    }
}

// Test
int main() {
   createGolombSequence();

   std::cout << golombSequence[777] << '\n';
   std::cout << golombSequence[7777] << '\n';
   std::cout << golombSequence[77777] << '\n';
}

We can even go one step ahead and use "compile time memoization", meaning, we will calculate the complete sequence at compile time. So, let the compiler do the work.

This will of course result in the fastest possible solution with the downside of high memory consumption and a little bit limited by the cababilities of the compiler.

Please see below. All Golomb value calculation is done at compile time. At runtime, we just use an ultrafast indexing operation:

#include <iostream>
#include <array>
#include <cstdint>

// We will calculate a Golomb sequence up to the below specified element
constexpr size_t MaxValues = 100000u;
using MyDataType = uint_fast16_t;
using GolombSequence = std::array<MyDataType, MaxValues>;

// Iterative Function to calculate a Golomb sequence using a DP table
constexpr GolombSequence createGolombSequence() {

    GolombSequence golombSequence{};
    golombSequence[1] = 1;
    for (int i = 2; i < MaxValues; ++i) {
        golombSequence[i] = 1 + golombSequence[i - golombSequence[golombSequence[i - 1]]];
    }
    return golombSequence;
}
// This is the Golomb Sequence
constexpr GolombSequence golombSequence = createGolombSequence();

// Test
int main() {

   std::cout << golombSequence[777] << '\n';
   std::cout << golombSequence[7777] << '\n';
   std::cout << golombSequence[77777] << '\n';
}

I added my code to Franks Benchmark. The result is dramatically outperforming everything else. The green line at 0ms is for the above algorithm.

Used benchmark code

#include <chrono>
#include <iostream>
#include <array>
#include <cstdint>

// We will calculate a Golomb sequence up to the below specified element
constexpr size_t MaxValues = 10000u;
using MyDataType = uint_fast16_t;
using GolombSequence = std::array<MyDataType, MaxValues>;

// Iterative Function to calculate a Golomb sequence using a DP table
constexpr GolombSequence createGolombSequence() {

    GolombSequence golombSequence{};
    golombSequence[1] = 1;
    for (int i = 2; i < MaxValues; ++i) {
        golombSequence[i] = 1 + golombSequence[i - golombSequence[golombSequence[i - 1]]];
    }
    return golombSequence;
}
// This is the Golomb Sequence
constexpr GolombSequence golombSequence = createGolombSequence();

inline int golombFast(size_t i) { return golombSequence[i]; };


int golom(int n)
{
    if (n == 1) {return 1;}
    return 1 + golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int>& golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

static void TestGolombFast(benchmark::State& state) {
  for (auto _ : state) {
    benchmark::DoNotOptimize(golombFast(state.range(0)));
  }
}
BENCHMARK(TestGolombFast)->DenseRange(1, 17, 2);



static void TestGolomb(benchmark::State& state) {
  for (auto _ : state) {
    benchmark::DoNotOptimize(golom(state.range(0)));
  }
}
BENCHMARK(TestGolomb)->DenseRange(1, 17, 2);

static void TestGolombS(benchmark::State& state) {
for (auto _ : state) {
    std::unordered_map<int, int> golomb;

    // Be extra-generous, ignore construction and destruction of the set
    auto start = std::chrono::high_resolution_clock::now();
    benchmark::DoNotOptimize(golomS(state.range(0), golomb));
    auto end = std::chrono::high_resolution_clock::now();

    auto elapsed_seconds =
      std::chrono::duration_cast<std::chrono::duration<double>>(
        end - start);

    state.SetIterationTime(elapsed_seconds.count());
  }
}
BENCHMARK(TestGolombS)->DenseRange(1, 17, 2);