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 reverses the given stack.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= size of the stack <= 10^{4}
-10^{9} <= Each element of the stack <= 10^{9}
Sum of N over all test cases doesn't exceeds 10^{6}
Array may contain duplicate elements.

Difficulty: MEDIUM
Tags: Data structures

Complete search
Skill types: Data structures

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

Starter code:
#User function Template for python3



from typing import List



class Solution:

    def reverse(self,st): 

        #code here

Solutions:
from typing import List

class Solution:

	def reverse(self, st):

		def rev(st):
			if len(st) == 1:
				return [st[0]]
			else:
				return [st.pop()] + rev(st)
		return rev(st)


from typing import List

class Solution:

	def reverse(self, st):
		return [st.pop()] + self.reverse(st) if st else []


from typing import List

class Solution:

	def reverse(self, s):
		return s[::-1]


from typing import List

class Solution:

	def helper(self, st, arr, n):
		if n == 0:
			return arr
		if n != 0:
			temp = st.pop()
			arr.append(temp)
			return self.helper(st, arr, n - 1)

	def reverse(self, st):
		arr = []
		n = len(st)
		self.helper(st, arr, n)
		return arr


from typing import List

class Solution:

	def reverse(self, st):
		return st[::-1]


from typing import List

class Solution:

	def addElementlast(self, st, x):
		if len(st) == 0:
			st.append(x)
			return
		top = st[-1]
		st.pop()
		self.addElementlast(st, x)
		st.append(top)

	def func(self, st):
		if len(st) <= 1:
			return st
		top = st[-1]
		st.pop()
		r = self.func(st)
		self.addElementlast(r, top)
		return r

	def reverse(self, st):
		return self.func(st)


from typing import List

class Solution:

	def reverse(self, st):
		if len(st) <= 1:
			return st
		n = st.pop()
		return [n] + self.reverse(st)


from typing import List

class Solution:

	def reverse(self, st):
		if st:
			temp = st.pop()
			self.reverse(st)
			self.help(st, temp)
		return st

	def help(self, st, temp):
		if not st:
			st.append(temp)
		else:
			a = st.pop()
			self.help(st, temp)
			st.append(a)


from typing import List

class Solution:

	def reverse(self, st):
		aux = []
		self.f(st, aux)
		return aux

	def f(self, st, aux):
		if not st:
			return
		aux.append(st.pop())
		self.f(st, aux)


from typing import List

class Solution:

	def helper(self, st, revSt):
		if not st:
			return revSt
		else:
			revSt.append(st.pop())
			return self.helper(st, revSt)

	def reverse(self, st):
		revStack = []
		return self.helper(st, revStack)


from typing import List

class Solution:

	def reverse(self, st):
		stack = []
		rev_stack = []
		for i in range(len(st)):
			stack.append(st[i])
		for j in range(len(stack)):
			s = stack.pop()
			rev_stack.append(s)
		return rev_stack


from typing import List

class Solution:

	def reverse(self, s):

		def rev():
			if len(s) > 0:
				x = s.pop()
				rev()
				insertatbottom(x)
			return s

		def insertatbottom(x):
			if len(s) == 0:
				s.append(x)
			else:
				ele = s.pop()
				insertatbottom(x)
				s.append(ele)
			return s
		return rev()


from typing import List

class Solution:

	def reverse(self, st):
		lst = []
		while st:
			lst.append(st[-1])
			st.pop()
		return lst


from typing import List

class Solution:

	def reverse(self, st):
		l = []

		def rev():
			k = st.pop()
			l.append(k)
			if st:
				rev()
		rev()
		return l


from typing import List

class Solution:

	def reverse(self, st):
		k = st.pop()
		if st:
			self.reverse(st)
		st.insert(0, k)
		return st


from typing import List

class Solution(object):

	def insertAtBottom(self, stack, num):
		if not stack:
			stack.append(num)
		else:
			top = stack.pop()
			self.insertAtBottom(stack, num)
			stack.append(top)
		return stack

	def reverse(self, stack):
		if stack:
			top = stack.pop()
			self.reverse(stack)
			self.insertAtBottom(stack, top)
		return stack


from typing import List

class Solution:

	def insert_at_bottom(self, stk, item):
		if len(stk) == 0:
			stk.append(item)
			return
		temp = stk.pop()
		self.insert_at_bottom(stk, item)
		stk.append(temp)

	def reverse(self, st):
		if len(st) == 0:
			return
		temp = st.pop()
		self.reverse(st)
		self.insert_at_bottom(st, temp)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		if not st:
			return st
		else:
			temp = st.pop()
			st = self.reverse(st)
			st = self.insert_at_bottom(st, temp)
			return st

	def insert_at_bottom(self, st, item):
		if not st:
			st.append(item)
		else:
			temp = st.pop()
			st = self.insert_at_bottom(st, item)
			st.append(temp)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		if len(st) == 0:
			return
		else:
			element = st.pop()
			self.reverse(st)
			self.insert(st, element)
			return st

	def insert(self, st, element):
		if len(st) == 0:
			st.append(element)
			return
		else:
			temp = st.pop()
			self.insert(st, element)
			st.append(temp)
			return


from typing import List

class Solution:

	def insert(self, st, ele):
		if len(st) == 0:
			st.append(ele)
			return
		top = st.pop()
		self.insert(st, ele)
		st.append(top)

	def reverse(self, st):
		if len(st) == 0:
			return st
		top = st.pop()
		self.reverse(st)
		self.insert(st, top)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		return f(0, st)

def f(i, st):
	if i < len(st) // 2:
		(st[i], st[len(st) - 1 - i]) = (st[len(st) - 1 - i], st[i])
	else:
		return st
	return f(i + 1, st)


from typing import List

class Solution:

	def reverse(self, st):
		arr = []
		for i in range(len(st)):
			arr.append(st.pop())
		for i in range(len(arr)):
			st.append(arr[i])
		return st


from typing import List

class Solution:

	def reverse(self, st):

		def rev(i, a):
			a.append(i)
			return
		a = []
		for i in st[::-1]:
			rev(i, a)
		return a


from typing import List

class Solution:

	def reverse(self, st):

		def appen(s, x):
			if len(s) == 0:
				s.append(x)
				return
			new = []
			while len(s) != 0:
				new.append(s.pop())
			s.append(x)
			while len(new) != 0:
				s.append(new.pop())
			return s

		def reve(s):
			if s:
				x = s.pop()
				reve(s)
				appen(s, x)
		reve(st)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		if len(st) == 1:
			return st
		reversed_st = [st[-1]] + self.reverse(st[:-1])
		return reversed_st


from typing import List

class Solution:

	def reverse(self, st):

		def insert(stack, temp):
			if len(stack) == 0:
				stack.append(temp)
				return
			val = stack.pop()
			insert(stack, temp)
			stack.append(val)

		def reversing(st):
			if len(st) == 1:
				return
			temp = st.pop()
			reversing(st)
			insert(st, temp)
		reversing(st)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		ans = [[]]

		def find(st, i):
			if i == len(st):
				return
			find(st, i + 1)
			ans[0].append(st[i])
			return
		find(st, 0)
		return ans[0]


from typing import List

class Solution:

	def reverse(self, st):
		if len(st) == 1:
			return st
		temp = st[-1]
		st.pop()
		self.reverse(st)
		self.insertAtBottom(st, temp)
		return st

	def insertAtBottom(self, st, temp):
		if len(st) == 0:
			st.append(temp)
		else:
			a = st[-1]
			st.pop()
			self.insertAtBottom(st, temp)
			st.append(a)
			return st


from typing import List

class Solution:

	def insert_at_bottom(self, st, x):
		if len(st) == 0:
			st.append(x)
		else:
			temp = st.pop()
			self.insert_at_bottom(st, x)
			st.append(temp)

	def reverse(self, st):
		self.reverse_util(st)
		return st

	def reverse_util(self, st):
		if len(st) != 0:
			x = st.pop()
			self.reverse_util(st)
			self.insert_at_bottom(st, x)


from typing import List

class Solution:

	def rev(self, st, newst):
		if len(st) == 0:
			return newst
		el = st.pop()
		newst.append(el)
		return self.rev(st, newst)

	def reverse(self, st):
		newst = []
		return self.rev(st, newst)


from typing import List

class Solution:

	def reverse(self, st):

		def insert(stack, ele):
			if len(stack) == 0:
				stack.append(ele)
				return
			x = stack.pop()
			insert(stack, ele)
			stack.append(x)
			return stack

		def backtrack(stack):
			if len(stack) == 1:
				return stack
			x = stack.pop()
			backtrack(stack)
			res = insert(stack, x)
			return res
		return backtrack(st)


from typing import List

class Solution:

	def reverse(self, st):
		return reversed(st)


from typing import List

class Solution:

	def insert_at_end(self, stk, data):
		if len(stk) == 0:
			stk.append(data)
			return
		d = stk.pop()
		self.insert_at_end(stk, data)
		stk.append(d)

	def reverse(self, st):
		if len(st) == 0:
			return
		d = st.pop()
		self.reverse(st)
		self.insert_at_end(st, d)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		resstack = []

		def rev(i):
			if i == len(st) - 1:
				resstack.append(st[i])
				return
			rev(i + 1)
			resstack.append(st[i])
		rev(0)
		return resstack


from typing import List

class Solution:

	def reverse(self, st):
		reverse = []
		self.reverse_stack(st, reverse)
		return reverse

	def reverse_stack(self, stack, reverse):
		if len(stack) == 0:
			return
		reverse.append(stack.pop())
		self.reverse_stack(stack, reverse)
		return


from typing import List

class Solution:

	def reverse(self, st):
		reverse = []
		while len(st) != 0:
			reverse.append(st.pop())
		return reverse


from typing import List

class Solution:

	def reverse(self, st):

		def reverseHelper(l, start, end):
			if start > end:
				return l
			if start == end:
				return l
			(l[start], l[end]) = (l[end], l[start])
			reverseHelper(l, start + 1, end - 1)
			return l
		return reverseHelper(st, 0, len(st) - 1)


from typing import List

class Solution:

	def reverse(self, st):
		g = []
		while st:
			g.append(st.pop())
		return g


from typing import List

class Solution:

	def reverse(self, st):
		while len(st) != 0:
			yield st[-1]
			st.pop(-1)


from typing import List

class Solution:

	def insertatbottom(self, st, v):
		if len(st) == 0:
			st.append(v)
			return
		val = st[-1]
		st.pop()
		self.insertatbottom(st, v)
		st.append(val)

	def util(self, st):
		if len(st) == 1:
			return
		val = st[-1]
		st.pop()
		self.util(st)
		self.insertatbottom(st, val)

	def reverse(self, st):
		self.util(st)
		return st


from typing import List

class Solution:

	def reverse(self, st):

		def insertLast(stack, no):
			if len(stack) == 0:
				stack.append(no)
				return
			e = stack.pop()
			insertLast(stack, no)
			stack.append(e)

		def helper(stack):
			if len(stack) == 1:
				return
			no = stack.pop()
			helper(stack)
			insertLast(stack, no)
		helper(st)
		return st


from typing import List

class Solution:

	def reverse(self, st):

		def helper(stack):
			if len(stack) == 1:
				return
			no = stack.pop()
			helper(stack)
			temp = []
			while stack:
				temp.append(stack.pop())
			stack.append(no)
			while temp:
				stack.append(temp.pop())
		helper(st)
		return st


from typing import List

class Solution:

	def reverse(self, st):

		def reverseStack(s, i):
			if i >= len(s) // 2:
				return
			(s[i], s[len(s) - 1 - i]) = (s[len(s) - 1 - i], s[i])
			reverseStack(s, i + 1)
		reverseStack(st, 0)
		return st


from typing import List

class Solution:

	def reverse(self, st):

		def hepler(ds, st):
			if not st:
				return ds
			ds.append(st[-1])
			return hepler(ds, st[:-1])
		return hepler([], st)


from typing import List

class Solution:

	def reverse(self, st):

		def rev(left, right, st):
			if left >= right:
				return st
			temp = st[right]
			st[right] = st[left]
			st[left] = temp
			rev(left + 1, right - 1, st)
			return st
		return rev(0, len(st) - 1, st)


from typing import List

class Solution:

	def reverse(self, st):

		def func(st):
			if not st:
				return
			p = st.pop()
			func(st)
			func2(st, p)
			return

		def func2(st, p):
			if not st:
				st.append(p)
				return
			top = st.pop()
			func2(st, p)
			st.append(top)
			return
		func(st)
		return st


from typing import List

class Solution:

	def reverse(self, st):
		(l, s) = ([], len(st) - 1)

		def rec(s, st, l):
			if s == -1:
				return
			l.append(st[s])
			rec(s - 1, st, l)
		rec(s, st, l)
		return l


from typing import List

class Solution:

	def reverse(self, st):

		def func(st, res):
			if not st:
				return
			while len(st) > 1:
				res.append(st.pop())
			last = st.pop()
			for i in range(len(res)):
				st.append(res[i])
			st.append(last)
			return
		func(st, [])
		return st


from typing import List

def reverse_stack_using_recursion(input_stack: []):
	if len(input_stack) == 0:
		return
	x = input_stack.pop(-1)
	reverse_stack_using_recursion(input_stack)
	append_start_stack(input_stack, x)

def reverse_main(input_stack: []):
	reverse_stack_using_recursion(input_stack)
	return input_stack

def append_start_stack(input_stack: [], x):
	if len(input_stack) == 0:
		input_stack.append(x)
		return
	popped_element = input_stack.pop(-1)
	append_start_stack(input_stack, x)
	input_stack.append(popped_element)

class Solution:

	def reverse(self, st):
		return reverse_main(st)


from typing import List

class Solution:

	def rev(self, st, ans):
		if not len(st):
			return
		num = st.pop()
		ans.append(num)
		self.rev(st, ans)
		return ans

	def reverse(self, st):
		ans = self.rev(st, [])
		return ans


from typing import List

class Solution:

	def reverse(self, st):

		def rev(idx, st, N):
			if idx >= N // 2:
				return
			(st[idx], st[N - idx - 1]) = (st[N - idx - 1], st[idx])
			rev(idx + 1, st, N)
		rev(0, st, len(st))
		return st


from typing import List

class Solution:

	def reverse(self, st):
		n = len(st)
		i = 0
		l = []
		while i < n:
			e = st.pop()
			l.append(e)
			i = i + 1
		return l


from typing import List

class Solution:

	def reverse(self, st):

		def f(st):
			if st == []:
				return []
			cur = st.pop()
			return [cur] + f(st)
		return f(st)


from typing import List

class Solution:

	def recStk(self, st, n, i, stk):
		if len(st) == 0 or i == n:
			return
		self.recStk(st, n, i + 1, stk)
		stk.append(st[i])

	def reverse(self, st):
		n = len(st)
		stk = []
		self.recStk(st, n, 0, stk)
		return stk


from typing import List

class Solution:

	def reverse(self, st):
		helper(st)
		return st

def helper(st):
	if len(st) <= 1:
		return
	val = st.pop()
	helper(st)
	reverseSt(st, val)

def reverseSt(st, val):
	if len(st) == 0:
		st.append(val)
		return
	tmp = st.pop()
	reverseSt(st, val)
	st.append(tmp)


from typing import List

class Solution:

	def pop_stack(self, stack, result):
		if not stack:
			return result
		else:
			item = stack.pop()
			result.append(item)
			return self.pop_stack(stack, result)

	def tail_rec_pop_stack(self, stack, result):
		if not stack:
			return result
		else:
			item = stack.pop()
			result.append(item)
			return self.tail_rec_pop_stack(stack, result)

	def reverse(self, st):
		return self.tail_rec_pop_stack(st, [])


from typing import List

class Solution:

	def reverse(self, st):

		def insert_bottom(stack, x):
			if not stack:
				stack.append(x)
				return stack
			else:
				a = stack.pop()
				stack = insert_bottom(stack, x)
				stack.append(a)
				return stack

		def rev(stack):
			if not stack:
				return stack
			else:
				x = stack.pop()
				stack = rev(stack)
				if not stack:
					stack.append(x)
					return stack
				else:
					return insert_bottom(stack, x)
		return rev(st)


from typing import List

class Solution:

	def reverse(self, st):
		if len(st) == 0:
			return st
		result = [st.pop()]
		return result + self.reverse(st)


from typing import List

class Solution:

	def reverse(self, st):

		def rec(st):
			if len(st) == 1:
				return [st.pop()]
			a = st.pop()
			return [a] + rec(st)
		return rec(st)


from typing import List

class Solution:

	def reverse(self, st):
		if len(st) <= 1:
			return st
		temp = st[-1]
		st.pop()
		reversed_stack = self.reverse(st)
		self.insertAtBottom(reversed_stack, temp)
		return reversed_stack

	def insertAtBottom(self, s, item):
		if len(s) == 0:
			s.append(item)
			return
		temp = s[-1]
		s.pop()
		self.insertAtBottom(s, item)
		s.append(temp)
		return