Reverse stack using recursion

Description:

Given a stack, reverse it using recursion.

解题方法：

通过递归，每次将top的元素pop出来，将其加入到栈的最底层。
如果加入到最低层？
通过递归，每层都出栈，直到栈为空。

Time Complexity：

O(n^2)

完整代码：

void reverse(stack<int>& S) {
    if(S.empty())
        return;
    int temp = S.top();
    S.pop();
    reverse(S);
    addToBottom(S, temp);
}

void addToBottom(stack<int>&S, int num) {
    if(S.empty()) 
        S.push(num);
    else {
        int temp = S.top();
        S.pop();
        addToBottom(S, num);
        S.push(temp);
    }
}