Analysing Space Complexity
In my opinion you are not quite right...

During the loop, when you return from foo(i), the spaces used by the call foo(i) is released (I mean, the stack pointer is back to the previous position).

So actually foo(i) only uses 1 more AR than foo(i - 1). The space cost should be O(n).

This can be verified by running the code with foo(25) and specify a stack of size 1 MB (disable all optimizations, of course). It will return normally within several seconds, without "stackoverflow". This is a proof that it's not using O(2^n) space.