to_sign_or_not_to_sign.cpp

// https://nauka.leprosorium.ru/comments/2349993/

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

long long f(int x) {
    if (x < 0) return 0;
    else if (x == 0) return 1;
    else return f(x-1) + f(x-2) + f(x-3) + f(x-4);
}

long long f2(int x) {
    if (x <= 0) return (x > 0) - (x < 0) + 1;
    else return f2(x-1) + f2(x-2) + f2(x-3) + f2(x-4);
}

void measure(const char* name, long long (*fn)(int)) {
    steady_clock::time_point begin = steady_clock::now();
    long long res = fn(30);
    steady_clock::time_point end = steady_clock::now();
    cout << name << " output " << res << " time " << duration_cast<microseconds>(end - begin).count() << endl;
}

int main() {
    measure("Naive", f);
    measure("Fancy", f2);
}