With such a function, when
grows, you can safely ignore the space taken by stack allocation.
On the heap, due to the recursive calls you have
memory(N) = 2*N + .. + 4 + 2
memory(N) = 2*N! (measured in
sizeof(int), of course).
So the function space complexity is
Sorry I made a blunder (many thanks to Patrice T
for spotting it). I actually multiplied what I have to add instead.
memory(N) = N(N+1)
And function space complexity is