Iterative Radix-2 FFT in C
Bit-reversal permutation bug
Keeping both a normal counter and the &quot;reversed counter&quot; is the right idea, but this implementation isn't quite right. For example, it might result in a sequence such as 0, 4, 2, 6, 1, 3, 5, 7 while the correct one is 0, 4, 2, 6, 1, 5, 3, 7.
A   B
000 000
100 100
010 010
110 110
001 001
011 101 &lt;&lt;&lt;
101 011 &lt;&lt;&lt;
111 111

There are various ways to do this without that bug, but some of them rely on instructions that are unlikely to be efficient (or even exist) on microcontrollers, such as leading zero count and shift-by-variable. I don't know what you can make work, and make efficient, since I don't know your microcontroller. Perhaps a recursive implementation of the bit-reversal permutation is better, but maybe not, given the often high cost of recursion on microcontrollers. I can only recommend trying some options, I don't know how they will work out in your specific case.
Also, see at the bottom for algorithmic changes.
Periodic test in the inner loop
By that I mean the condition of this if statement:

if (i % even_to_odd == 0) {
    to_even = 2 * i;
    current_rotation = complex_init(1, 0);
}


While it is the case that a remainder operation with a power of two on the right hand side can be efficient, that only applies when the compiler knows it's dealing with a power of two. Hypothetically, a compiler could detect this case, but there is not much hope for that happening. GCC 10 compiling for x64 (I realize you're not targeting that, but that's not really the point, it's about the compilers ability to reason above the set of values even_to_odd could have and how to use that information) makes this for example:
    mov     eax, ecx
    xor     edx, edx
    div     ebx
    test    edx, edx
    jne     .L41

That's not good, and it would be worse on a microcontroller. Since you know that even_to_odd is a power of two, you could write the condition like this: (i &amp; (even_to_odd - 1)) == 0. If GCC 10 cannot do this automatically, it is not likely that the various vendor-specific compilers for some microcontrollers can do it either, as they are usually weaker in that regard.
Benchmarking note

Seems to be 20-40% faster on my desktop than the recursive version I wrote

By all means test it on your desktop, but when option B is faster than option A on a desktop, that is no guarantee at all that that will still be true on the microcontroller. Even between different desktops there is no such guarantee, if they have processors with a different micro-architecture, for example AMD Zen vs Intel Skylake. Benchmarking the code on your desktop can easily trick you into making decisions that are bad for the microcontroller.
Algorithmic changes
The Stockham FFT avoids an explicit bit-reversal permutation, removing the need to implement it efficiently. On the other hand, it accesses memory in a different way and needs temporary work-space. Maybe it's good for your application, or maybe not, I'm not sure.