Static variable representing program state accessed with multiple functions
Since it's a single-threaded algorithm, I think you could simplify things a bit to avoid all the state-checking. Unless you're reading the state from another thread, you don't really need to keep track of it at all. You could simply make perform_check_needed_for_algorithm return a bool:

for (;;)
{
    /* info.state = FIRST_STATE; */
    perform_first_state_function();
    /* info.state = SECOND_STATE; */
    perform_second_state_function();
    /* info.state = THIRD_STATE; */
    if (perform_check_needed_for_algorithm())
    {
        /* info.state = FINAL_STATE; */
        break;
    }
}


The commented-out state assignments are just there to show what's happening at each stage. Although a state machine's inner functions ought to be responsible for updating the state, in an example as simple as this, it's arguably more readable to update the state in the outer function.

If you need access to the state from another thread, then you'll need to update it using atomic operations, and mark it as volatile.

Afterthought:
perform_second_state_function doesn't always advance the state. It fails once ALLOWED_ATTEMPTS is exceeded. However, it dumps you back into the outer loop, and dives straight back into perform_second_state_function because state.info is still SECOND_STATE. Bit of a design error there IMO - it will keep trying no matter what.