Unlike its main rival the Z80, the 6502 had a size limit of 256 bytes for the hardware stack.
The 6502 stack is mainly meant as a return stack and for register preservation - which usually isn't a lot on a CPU with just 3 registers. It lacks all features for stack relative addressing (*1). A limitation not really a hindrance as the 6502 was focused on embedded, an area where dynamic memory allocation and variable parameter passing is not common.
That sounds like a very tight limit, but in my experience, it was never actually an issue; by the time you were trying to do anything complex enough to exceed it, you would run out of 64K RAM before running out of the 256-byte stack.
For embedded, games and runtimes like BASIC that's certainly true. It can get tricky with ALGOL derivative languages trying to (mis-)use the machine stack for data storage. That's why most of those language runtimes, like Pascal, used a separate data stack.
But my experience is not necessarily universal. So, did anyone ever run out of stack space on a 6502?
Let's say it's hard, but possible. Two examples from the Apple II world:
While Applesoft itself uses only a few levels for subroutine calling, it does use the stack for bookkeeping of
- Temporary Variables (in expressions)
- FOR/NEXT Loops
- Subroutine Calling
Space requirements are, as the original Applesoft Manual (Blue Book) states in Appendix D - Space hints:
As a result, a few levels of nested FOR/NEXT and calculations can put up a heavy stack load - and when structured with GOSUB even more. This has been experienced notably by some programs walking matrices, doing complex calculations.
Already in a basic matrix multiplication, like shown in line 5 of this Rosetta Code snippet may eat up ¼ of the stack:
(Indentation added for readability)
FOR I = 1 TO M: | +16 bytes
FOR J = 1 TO P: | +16 bytes
FOR K = 1 TO N: | +16 bytes
AB(I,J) + | + 4 bytes
(A(I,K) * B(K,J)): | +12 bytes
That's 64 bytes at maximum depth. Add another 6 for each level of a subroutine it's in - which for that kind of stuff is extremely common, as it's needed over and over. And that's just a multiplication on the inside. Imagine some using more complex formula for 3D calculation in graphics or astronomical programs makes it easy to see how BASIC can end up reporting an "OUT OF MEMORY" error.
These numbers may as well be valid for other 6502 MS-BASIC derivatives.
ProDOS in turn may use up to a quarter (~64) of the stack during execution, thus stressing the available space even more. While ProDOS calls usually don't happen within calculations, it does need more stack during execution than bare-bones BASIC.
Yes, it may happen with non-trivial BASIC programs.
*1 - Although that can be emulated to some degree by moving the stack pointer to X and using indexed addressing, but that quickly gets cumbersome when needing anything past the most basic byte fetch.