3 ms·
> Recursion is required to implement non-primitive recursive procedures This is very untrue. While loop and a stack. > cannot be implemented with a fixed numb
by qsort 5y ago
> Recursion is required to implement non-primitive recursive procedures
This is very untrue. While loop and a stack.
> cannot be implemented with a fixed number of state variables
Of course it can't, any function outside DSPACE(O(1)) can't. The fact that you have an implicit call stack doesn't change the space complexity.
- ZephyrP 5y ago> This is very untrue. While loop and a stack. >> You can still simulate > any function outside DSPACE(O(1)) can't The space complexity of the algorithm is only incidentally related to the number of unique variables required to represent it's state. You said it best: > The fact that you have an implicit call stack doesn't change the space complexity