With such a function, when
N
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
that is
memory(N) = 2*N!
(measured in sizeof(int)
, of course).
So the function space complexity is
O(N!)
Sorry I made a blunder (many thanks to
Patrice T for spotting it). I actually multiplied what I have to add instead.
So
memory(N) = N(N+1)
And function space complexity is
O(N^2)