|
|
|
|
|
|
by qsort
1726 days 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. |
|
|
>> 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