[Solved] Recursive C function

Let’s construct our number that doesn’t have three consecutive ones from left to right.

It necessarily starts with at most two 1s, so it starts with either no 1s, a single 1, or two 1s. In other words, our number starts with either 0, 10 or 110. In all of these cases, the only restriction for the remainder of the number is that it doesn’t contain any three consecutive ones, so this allows us to apply the same function recursively:

#include <stdint.h>
#include <stddef.h>

uint64_t nothreeconsecutive(int n) {
    if (n <= 2) return 1 << n;
    return nothreeconsecutive(n-1) + nothreeconsecutive(n-2) + nothreeconsecutive(n-3);
}