Example for foo(5) ,when foo(4) is called in loop ,
it will have highest Depth
For foo(4), foo(3) will have Highest depth.
for foo(3) ,foo(2) will have highest depth.
for foo(2),foo(1) has highest depth.
foo(1) just execute loop 1 time and call foo(0).
So height of foo(2) is 3.
So height of foo(3) is 4.
height of foo(4) is 5.
height of foo(5) is 6.
For foo(n) we occupy approx n+1 lvls in tree
and so n+1 stack records and each record has space complexity of O(1)
as no extra space is used.
So overall Space complexity = Height of tree x Space complexity of each lvl
=O(n x 1)
=O(n)