Reverse a stack without using extra space (recursion can be used).

Solution #1: Even recursion will take extra space, but, the purpose of the question is to come up with a recursive implementation. First, we will implement a function "insertAtBottom()" which inserts an element at the bottom of the stack. And then we will use this function to implement "reverseStack()". Here is the code,

Algo:
- recursively empty the stack.
- add elements back using "insertAtBottom()"

void insertAtBottom(stack& s, int x)
{
    if(s.empty())
    {
        s.push(x);
        return;
    }

    int a = s.top();
    s.pop();
    insertAtBottom(s, x);
    s.push(a);
}

void reverseStack(stack& s)
{
    if(s.empty())
        return;

    int a = s.top();
    s.pop();
    reverseStack(s);
    insertAtBottom(s, a);
}

int main()
{
    stack s;

    s.push(5);
    s.push(4);
    s.push(2);
    s.push(7);
    s.push(9);

    //current stack: top - 9 7 2 4 5 - bottom
    
    reverseStack(s);

    //reversed stack: top - 5 4 2 7 9 - bottom
    
    while(!s.empty())
    {
        printf("%d ", s.top());
        s.pop();
    }

    printf("\n");

    return 1;
}