Where does a C-like language without heaps belong in the automata hierarchy?
Assuming we have an unbounded stack and pointers, it's a Turing machine. Since the stack is unbounded, we can get by very easily using a CPS-like style. Whenever we need to allocate memory, we'll just do it on a stack frame, then continue with the computation on the next. If our stack frames were bounded in size, of course we'd be a finite state machine. Here's a little example machine with no imports whatsoever (including no malloc). Of course on a real computer we'll eventually get a stack overflow with this. This model could be easily adjusted to have correct space usage, by adding a new stack frame only once we need to allocate.

#define NULL 0

typedef enum {
    ZERO,
    ONE,
} symbol;

typedef struct tape {
    struct tape* left;
    symbol sym;
    struct tape* right;
} tape;

typedef enum {
    A, B, DONE
} state;


int handle(tape* tape, state state);
int move_right(tape* tape, state state);
int move_left(tape* tape, state state);

int main() {
    tape start = {NULL, ZERO, NULL};
    return handle(&amp;start, A);
}

int handle(tape* tape, state state) {
    // do some stuff
    switch (state) {
        case B:
            switch(tape-&gt;sym) {
                case ZERO:
                    return move_left(tape, DONE);
                case ONE:
                    tape-&gt;sym=ONE;
                    return move_left(tape, A);
            }
            break;
        case A:
            switch(tape-&gt;sym) {
                case ZERO:
                    tape-&gt;sym=ONE;
                    return move_right(tape, B);
                case ONE:
                    tape-&gt;sym=ZERO;
                    return move_right(tape, B);
            }
            return move_right(tape, state);
        case DONE:
            return tape-&gt;sym;
    };
};

int move_right(tape* tape0, state state) {
    tape new_tape;

    if (tape0-&gt;right == NULL) {
        new_tape = (tape){tape0, ZERO, NULL};
        tape0-&gt;right = &amp;new_tape;
        return handle(&amp;new_tape, state);
    } else {
        return handle(tape0-&gt;right, state);
    }
};

int move_left(tape* tape0, state state) {
    tape new_tape;

    if (tape0-&gt;left == NULL) {
        new_tape = (tape){NULL, ZERO, tape0};
        tape0-&gt;left = &amp;new_tape;
        return handle(&amp;new_tape, state);
    } else {
        return handle(tape0-&gt;left, state);
    }
};