A (non-tail) recursive function actually needs a reentrant mechanism to implement the semantics of calling itself; this mechanism is a stack.
Without recursive functions, we have a bounded call depth and thus don't actually need a growable stack; a fixed-size array suffices.
We take for granted that function calls are always implemented with a stack, because that's how processors work today, but it could have been done differently. We could imagine an alternative timeline with much restricted functions and no implicit call stack.
And indeed, tail recursive functions are usually implemented with tail call elimination, in which the caller reuses the stack frame of the callee; function call becomes a simple goto, which transforms recursion into loop iteration. If we didn't have an implicit stack we could still have tail recursive functions (and a bounded number of non-tail calls), and manage other recursion cases with explicit stacks.
1) the quicksort algorithm which was used was a recursive version, and relied on local variables to do its job.
2) in the discussed BASIC implementation, local variables are translated to global variables (probably with some form of prefixing based on the function using it to avoid name clashes). This means that functions in that language are never fully reentrant, and that somehow an explicit variable stack has to be implemented to recover the ability to recurse without overwriting variable prematurely.
Note: I initially had a doubt wrt reentrancy, as I had knowledge of this concept in the context of multithreading (I think it actually came up originally in that context), and indeed having concurrent uses of the same function relying on some global variable is problematic, but here there isn't any kind of concurrency. However, global variables can be a problem in the situation outlined above. Another possible issue, although not present here, is when a function F uses a global variable, and accept a function pointer. If that pointer is pointing to a function making a call to F somehow, then lack of reentrancy could also be a problem.
Without recursive functions, we have a bounded call depth and thus don't actually need a growable stack; a fixed-size array suffices.
We take for granted that function calls are always implemented with a stack, because that's how processors work today, but it could have been done differently. We could imagine an alternative timeline with much restricted functions and no implicit call stack.
And indeed, tail recursive functions are usually implemented with tail call elimination, in which the caller reuses the stack frame of the callee; function call becomes a simple goto, which transforms recursion into loop iteration. If we didn't have an implicit stack we could still have tail recursive functions (and a bounded number of non-tail calls), and manage other recursion cases with explicit stacks.
See for example pratt parsing https://matklad.github.io/2020/04/13/simple-but-powerful-pra... which uses the implicit call stack, and contrast with Dijkstra's shunting yard algorithm https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... which is the same thing but with an explicit stack. If we didn't have a call stack, we could always program in Dijkstra's style and be none the wiser.