Reverse a Stack

Medium

You are given a stack St. You have to reverse the stack using recursion.

Example 1:

Input:
St = {3,2,1,7,6}
Output:
{6,7,1,2,3}

Example 2:

Input:
St = {4,3,9,6}
Output:
{6,9,3,4}

Your Task:

You don't need to read input or print anything. Your task is to complete the function Reverse() which takes the stack St as input and returns the reversed stack.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= size of the stack <= 10⁴
-10⁹ <= Each element of the stack <= 10⁹
Sum of N over all test cases doesn't exceeds 10⁶
Array may contain duplicate elements.