Procedural or not was more of a spectrum. If you look at early BASICs, for example, they had GOSUB, and it could recurse, so there was a return-address stack. But GOSUB did not have any provisions to pass arguments or return values - it was just a GOTO that remembered where it came from; you had to use globals to pass data around. So if you wanted a data stack (i.e. locals), you had to rig your own with arrays.

OTOH early FORTRAN had procedures with arguments and results, but no recursion.

Structural or not was also not necessarily all-in. FORTRAN and BASIC both had for-loops before they had structured conditionals.