the art of
Algorithm
Notes on Analysis and Design

Home
Articles
Articles related to Algorithms and Design
Implementation
Implementation in C++ and Python
Languages
Nuances of Languages
Sorting Stack Using Recursion

Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def createstack():
	s=[]
	return s
def push(stack,item):
	if len(stack) !=0:
		return 0
	stack.append(item)

def pop(item):
	if len(stack)==0:
		return 0
	return stack.pop()
def sortstack(s):
	if stack is not None:
		temp=pop(s)
		sortstack(s)
		sortedinsert(s,element)
def sortedinsert(s,element):
	if s is None or element>s.top():
		push(s,element)
	else:
		temp=pop(s)
		sortedinsert(s,element)
		push(s,temp)
#Main program
s =createstack()
push(stack, str(20))
push(stack, str(20))
push(stack, str(30))
print sortstack(s)

•