In the early days of computing, programs did not have a call stack and code was not usually re-entrant. No recursion. So, finding a place to store state was tough. This is still seen in some embedded code.
It's all Von Neumann's fault. The program is stored in main memory, and he makes a big point that this means the program can modify itself. So early programming languages, operating systems, and CPUs tended to have support for that. Von Neumann didn't think of index registers. Array access involved code modification.
It took a while for index registers to become a standard computer feature. The first one was in the Manchester Mark I, but they were, for too long, a "high end" feature. The IBM 650, IBM 1401, and the Intel 8080 lacked them.[1] Building in an extra adder cost money.
The PDP-8 has a fun method of returning from subroutines: every subroutine has a spare word allocated at the beginning of it, and it gets the return address written to it when the subroutine is called. Returning from the subroutine is therefore a matter of jumping to the written address. This lets you call a chain of subroutines without a stack, but of course recursion is impossible.
There was an interesting controversy surrounding the Algol-60 report. It seems many members of the committee wanted to be able to create implementations of the language that used only static allocations for activation records, but in the "Amsterdam plot," they sneaked into the report the possibility for recursive procedure definitions which require dynamically allocated activation records (not all machines had efficient stacks!). I don't remember where I first learned about this, it might have been this https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
UNIVAC 1100 series machines had a Store Location Jump instruction which did that. The return point was stored into the first word of the subroutine. Fortunately, you didn't have to use that.
Stacks were, for a long time, controversial. What if you ran out of memory? Some rare compilers, such as Modula 1 for the PDP-11, computed the stack size for each task. If you wanted to recurse, you had to give a recursion limit. Async, the early years.
Stacks work well now because we now have lots of memory and address space. Early machines lacked that luxury.
I used a compiler 30 years ago for an embedded target that didn't support recursion.
There was a tradeoff. By nixing recursion the compiler could perform variable folding optimizations that would be impossible with recursion. That's because without recursion the call tree is an acyclic graph. The result is variables are held in registers and a tiny scratchpad instead of being pushed on a stack.
> There was a tradeoff. By nixing recursion the compiler could perform variable folding optimizations that would be impossible with recursion.
I don't think this is a real tradeoff. Your optimization clearly depends on whole-program compilation anyway, so programs that do not involve non-tail recursion can still be optimized as such.
To add to the history lesson, Herr Doktor Professor Djikstra's infamous "Go To Statement Considered Harmful" should perhaps have been titled "Call Stack Considered Very Useful".
It's worth reading with this understanding, and of course, it is a must to follow through with Dr. Knuth's equally seminal "Structured Programming with go to Statements", in which Djikstra is briefly quoted to qualify and clarify his position on the matter.
In the early days of computing, programs did not have a call stack and code was not usually re-entrant. No recursion. So, finding a place to store state was tough. This is still seen in some embedded code.
It's all Von Neumann's fault. The program is stored in main memory, and he makes a big point that this means the program can modify itself. So early programming languages, operating systems, and CPUs tended to have support for that. Von Neumann didn't think of index registers. Array access involved code modification.
It took a while for index registers to become a standard computer feature. The first one was in the Manchester Mark I, but they were, for too long, a "high end" feature. The IBM 650, IBM 1401, and the Intel 8080 lacked them.[1] Building in an extra adder cost money.
[1] https://en.wikipedia.org/wiki/Index_register