Size of stack required is ?

Question

A(n)
{      
    if(n>=1)
     {
        A(n-1); // statement 1
        print n; //statement 2
        A(n-1);// statement 3
     }
}

Answer 1

Size of stack is of the order of the number of recursive calls which are currently live. (It is not equal because we save many info on the stack during a call like local variables, return address etc. )

 Here, we have two recursive calls with value (n-1) for input n. But before the second one starts, the first one finishes. So, total number of recursive calls for n can be given by

Solve recurrence T(n) = 2T(n-1) + 1 (1 for the stack space required for the current process) with T(0) = 1.

and the number of live recursive calls (recursion depth) is given by

T(n) = T(n-1) + 1 which is O(n).

Comments

i got the size of the stack as  n+1 although it is O(n) ...no worry

---

I am unable to understand why we formed a recurrence relation here when actually the stack size is n just in each case so why is there a need of using asymptotic notation for this .

---

The time complexity is O(2ⁿ) , am I correct ?