`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 + 2that 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)