DATA STRUCTURE - RECURSION BASICS Some computer programming languages allows a module or function to call itself This technique is known as recursion
We will take only a superficial look at recursion in this course since it provides a very neat way to represent certain useful numerical functions and data
A function is said to be recursive if it calls itself again and again within its body whereas iterative functions are loop based imperative functions 2
Ming Zhang“ Data Structures and Algorithms “ Commonly used to deal with data which has recursive Non recursive implementation of recursive algorithm
11 3 Example: recursive implementation of the sum between two integers the stack of ARs is used as a temporary “data structure” in which to store the
28 mar 2013 · 4 2 4 Implementing Recursion C++ is used here strictly as a tool to illustrate data structures concepts In particu-
Which data structure is used by the compiler to implement recursion? (a) hash table (b) priority queue (c) queue (d) search tree (e) stack
Recursion is another, typically more favored, solution, which is actually implemented by a stack Memory Management Any modern computer environment uses a
71784_3chapter3_EN.pdf https://courses.edx.org/courses/PekingX/04830050x/2T2014/
3OTÓ @NGTÓȐ *GRG 9RX[IR[XOY GTJ GRÓUXORNSY Ȑ
Data Structures
and Algorithms"3ͤ
Instructor: Ming Zhang
Textbook Authors: Ming Zhang, Tengjiao Wang and Haiyan Zhao Higher Education Press, 2008.6 (the "Eleventh Five-Year" national planning textbook) 2 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ 澧
Chapter 3 Stacks and Queues
Stacks
Applications of stacks
²Implementation of Recursion
using Stacks
Queues
Stacks and
Queues
Chapter 3
3 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ
Linear lists with limited operation
Stack
²Operation are permitted only on one
end
Queue
²Operation are permitted only on two
ends
Stacks and
Queues
Chapter 3
4 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ
Definition of stack
Last In First Out
²A linear list with limited access port
Main operation
²push澝pop
Applications
²Expression evaluation
²Elimination of recursion
²Depth-first search
3.1 Stacks
k1 ... Ki Ki+1
Stack top
Stack bottom
pop push k0
Stacks and
Queues
Chapter 3
5 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ
Abstract data type of stacks
3.1 Stacks
template
class Stack { public: // Operation set of stacks void clear(); // Change into an empty stack bool push(const T item); // push item into the stackͫreturn true if succeed, otherwise false bool pop(T& item); // pop item out of the stackͫ return true if succeed, otherwise false bool top(T& item); // read item at the top of the stack, return true if succeed, otherwise false bool isEmpty(); // If the stack is empty return true bool isFull(); // If the stack is full return true }; Stacks and
Queues
Chapter 3
6 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Railway station problem
Judge whether the trains go out of the station in the right order? ²http://poj.org/problem?id=1363
1 PUMLQV QXPNHUHG MV 12"BQ JR LQPR POH PUMLQ LQ RUGHU ͫgiven an arrangementͫjudge whether the trains go out of the station in the right order? 3.1 Stacks
5, 4, 3, 2, 1 1, 2, 3, 4, 5
Railway station
B A Stacks and
Queues
Chapter 3
7 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Use legal reconstruction to find conflicts
3.1 Stacks
1 2 3 1 2 3 4 4
8 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Question
If the order of the item pushed into the stack is 1,2,3,4ͫthen what is the order of the item
popped out of the stack ? There is an original input sequence 1ͫ2ͫ"ͫn ͫyou are required to get the output sequence of p1ͫp2ͫ"ͫpn (They are a permutation of 1ͫ 2 ͫ"ͫn)using a stack. If there exists subscript i ͫjͫkͫwhich meet the condition that iPj legal or not( 3.1 Stacks
9 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Implementation of stacks
Array-based Stack
²Implemented by using vectorsͫis a
simplified version of sequential list The size of the stack
²The key point is to make sure which end as
the stack top ²Overflow, underflow problem
Linked Stack
²Use single linked list for storageͫin which the direction of the pointer is from stack top down 3.1 Stacks
10 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ The class definition of Array-based Stack
3.1.1 Array-based Stack
template class arrStack : public Stack { private: // storage of Array-based Stack int mSize; // the number of elements that the stack can have at most int top; // stack topͫshould be small than mSize T *st; // array to put stack element public: // implementation of the operation of the Array-based Stack arrStack(int size) { // creates an instance of Array-based Stack with given size mSize = size; top = -1; st = new T[mSize]; } arrStack() {// creates an instance of Array-based Stack top = -1; } ~arrStack() { delete [] st; } void clear() { top = -1; } // clear the stack } 11 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Array-based Stack
The index of the last element pushed
into the stack is 4ͫ followed by 3,2,1 in order 3.1.1 Array-based Stack
1 2 3 Stack top
Stack bottom 4 12 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Overflow of Array-based Stack
Overflow
²When you perform push operation on a
full stack (that already has maxsize elements), overflow will occur. Underflow
²When you perform pop operation on an
empty stack, underflow will occur. 3.1.1 Array-based Stack
13 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Push 3.1.1 Array-based Stack
bool arrStack::push(const T item) { if (top == mSize-1) { // the stack has been full cout << ȔStack overflow" << endl; return false; } else { //push new element into the stack and modify the pointer of the stack top st[++top] = item; return true; } } 14 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Pop 3.1.1 Array-based Stack
bool arrStack::pop(T & item) { // pop if (top == -1) { // the stack is empty cout << " 4 -... "-ř ...Ũ-
pop "<< endl; return false; } else { // Get top value and decrease top by 1 item = st[top--]; return true; } } 15 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Definition of Linked Stack
Use single linked list for storage The direction of the pointer is from stack top down 3.1.2 Linked Stack
Stack top
Kn-1 Kn-2 K1 K0 16 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Construction of Linked Stack
3.1.2 Linked Stack
template class lnkStack : public Stack { private: // storage for linked stack Link* top; //Pointer which points to the stack top int size; // the number of elements that the stack can have at most public:// implementation of the operation of the linked Stack lnkStack(int defSize) { // constructed function top = NULL; size = 0; } ~lnkStack() { // destructor function clear(); } } 17 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Push 3.1.2 Linked Stack
Link(const T info, Link* nextValue) { // constructed function with 2 parameters data = info; next = nextValue; } // implementation of push operation of linked stack bool lnksStack:: push(const T item) { Link* tmp = new Link(item, top); top = tmp; size++; return true; } 18 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Pop 3.1.2 Linked Stack
// implementation of pop operation of linked stack bool lnkStack:: pop(T& item) { Link *tmp; if (size == 0) { cout << " 7OH VPMŃN LV HPSP\ \RX ŃMQ·P SRS"<< endl; return false; } item = top->data; tmp = top->next; delete top; top = tmp; size--; return true; } 19 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Comparison of Array-based Stack and Linked Stack Time efficiency
²All operations only take constant time
²Array-based Stack and Linked Stack have
almost the same time efficiency Space efficiency
²The length of an Array-based Stack is fixed
²The length of a Linked Stack is variable,
with extra structural cost 3.1 Stacks
20 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Comparison of Array-based Stack and Linked Stack In real applicationsͫArray-based Stack is more widely used than Linked Stack ²It is easy for Array-based Stack to perform relative replacement according to the position of stack top , quickly position and read the internal element ²The time taken for Array-based Stack to read internal element is O(1). And the Linked stack has to walk along the chain of pointers, and is slower than Array-based Stack . It takes O(k) time to read the kth element. In general, the stack does not allow the
internal operation, can only operate in the stack top 3.1 Stacks
21
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Question͵ functions about stack in STL
Top function gets the element of the stack top and returns the result back to the user Pop function pops a element out of the stack
topͧif the stack is not emptyͨ ²Pop IXQŃPLRQ LV ÓXVP MQ RSHUMPLRQ MQG GRHVQ·P UHPXUQ the result ²pointer = aStack.pop()( Error͜
Why does STL divide these two operations(
Why not provide ptop(
3.1 Stacks
22
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Applications of stacks
Characteristic of stackslast-in first-out ²Embodies the transparency between elements
Commonly used to deal with data which
has recursive structure ²DFSevaluate the expression
²Subroutine / function call management
²Elimination of recursion
3.1 Stacks
23
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Evaluate the expression
Recursive definition of expressions
²The basic symbol set {0ͫ1ͫ"ͫ9ͫ+ͫ-ͫ* ͫ/ͫͧͫͨ}
²Grammar set{ , ,
, , } The infix expression 23+(34*45)/(5+6+7)
Postfix expression 23 34 45 * 5 6 + 7 + / +
3.1 Stacks
24
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Infix expression
Infix expression
4 * x * (2 * x + a) ² c ²Operator in the middle
²Need brackets to change
the priority 3.1 Stacks
- + c 4 x a
2 x * * * 25
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Syntax formula for infix expression
3.1 Stacks
Ī= + | - | Ī= < factor > * | < factor > < factor > / | < factor > < factor > Ī= < constant > < constant > Ī= | Ī= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 26
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Graphical representation for expression recursion 3.1 Stacks
expression term + ͬ term * / factor factor expression ( ) digit 27
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Postfix expression
Postfix expression
4 x * 2 x * a + * c ² ²Operators behind
²No need for brackets
3.1 Stacks
- + c 4 x a
2 x * * * 28
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Postfix expression
Ī= + | - | Ī= < factor > * | < factor > < factor > / | < factor > < factor > Ī= < constant > < constant > Ī= | Ī= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.1 Stacks
29
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Evaluating a postfix expression
23 34 45 * 5 6 + 7 + / + = ?
Calculation characteristics ( The main differences between infix and postfix expression ( 23 + 34 * 45 / ( 5 + 6 + 7 ) = ?
23 34 45 * 5 6 + 7 + / + = ?
3.1 Stacks
postfix expression to be handled͵ 23 / 45 5 6 7 * ͦ ͦ ͦ 34
change of the stack state 1530 11 18 85 108
calculation result 31
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Evaluating a postfix expression
Loopread symbol sequences of expressions
ͧMVVXPH ´ µ MV POH HQG RI POH LQSXP VHTXHQŃHͨ ͫand analyze one by one according to the
element symbol read 1.When an operand is metͫpush
2.When an operator is met, pop twice and get two
operands, calculate them using the operator. And finally push the result into the stack. FRQPLQXH POH SURŃHVV MNRYH XQPLO POH V\PNRO ´ ͼµ LV PHPͫ then the value of the stack top is the value of the input expression 3.1 Stacks
32
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ The class definition of postfix calculator
3.1 Stacks
class Calculator { private: Stack s;//the stack is used for pushing and storing operands // push two operands opd1 and opd2 from the stack top bool GetTwoOperands(double& opd1,double& opd2); // get two operands, and calculate according to op void Compute(char op); public: Calculator(void){} ; // creates calculator instance and construct a new stack void Run(void); // read the postfix expression, ends when meet "=" void Clear(void); // clear the calculator to prepare for the next calculation }; 33
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ The class definition of postfix calculator
3.1 Stacks
template bool Calculator::GetTwoOperands(ELEM& opnd1, ELEM& opnd2) { if (S.IsEmpty()) { cerr << "Missing operand!" < ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ The class definition of postfix calculator
3.1 Stacks
template void Calculator::Compute(char op) { bool result; ELEM operand1, operand2; result = GetTwoOperands(operand1, operand2); if (result == true) switch(op) { case '+' : S.Push(operand2 + operand1); break; case '-' : S.Push(operand2 - operand1); break; case '*' : S.Push(operand2 * operand1); break; case '/' : if (operand1 == 0.0) { cerr << "Divide by 0!" << endl; S.ClearStack(); } else S.Push(operand2 / operand1); break; } else S.ClearStack(); } 35
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ The class definition of postfix calculator
3.1 Stacks
template void Calculator::Run(void) { char c; ELEM newoperand; while (cin >> c, c != '=') { switch(c) { case '+': case '-': case '*': case '/': Compute(c); break; default: cin.putback(c); cin >> newoperand; Enter(newoperand); break; } } if (!S.IsEmpty()) cout << S.Pop() << endl; // print the final result } 36
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Question
1. Stack is usually implemented by
using single linked list. Can we use doubly linked list? Which is better( 2. Please summarize the properties
of prefix expression, as well as the evaluation process. 37
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3 Stacks and Queues
Stacks
Application of stacks
²Implementation of Recursion using
Stacks
Queues
38
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
Transformation from recursion to non-recursion The principle of recursive function
Transformation of recursion
The non recursive function after
optimization 39
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
Another study of recursion The principle of recursive function
Factorial
Exit of recursion
²End condition of recursion is when the minimal problem is solved ²More than one exits are permitted
Rule of recursion
ͧRecursive body + bounded functionͨ ²Divide the original problem into sub problems ²Ensure that the scale of recursion is more and more closer to the end condition 40
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
Non recursive implementation of recursive algorithm The principle of recursive function
- Establish iteration - Transformation from recursion to non-recursion Non recursive implementation of factorial
How about the problem of Hanoi Tower᧻
41
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
Recursion program for Hanoi tower problem
hanoi(n,X,Y,Z)
²Move n disk
²Move the disk from pillar X to pillar Z
²X澝Y澝Z can be used to place disks temporarily Big disks cannot be put on small disks
Such as hanoi(2 ¶%· ¶F· ¶$· ²Move 2 disks from pillar B to pillar A
The principle of recursive function
http://www.17yy.com/f/play/89425.html 42
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
void hanoi(int n, char X, char Y, char Z) { if (n <= 1) move(X,Z); else { 22 JUTȑR SU\O RNO RGXÓOYR JOYQ UT L GTJ SU\O RNO ROLR T-1 disk to Y
hanoi(n-1,X,Z,Y); move(X,Z); //move the largest disk on X to Z hanoi(n-1,Y,X,Z); // move the n-1 disk on Y to Z } } void move(char X, char Y) // move the disk on the top of pillar x to pillar Y { cout << "move" << X << "to" << Y << endl; } 3.1.3 Transformation from recursion to non-recursion
43
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
Operating diagram of Hanoi recursive subroutine 3.1.3 Transformation from recursion to non-recursion
Execute the instructions of Hanoi program
Exchange information with subroutine via stack
k1 ... Ki Ki+1 Stack top
Stack bottom
pop push k0 44
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
H A,B,C
H A,C,B
Call subroutine
recursively 3 2 H A,B,C
1 Call subroutine
move(A,C) return move(A,B) H C,A,B
1 move(C,B) return return move(A,C) H B,A,C
2 H B,C,A
1 move(B,A) return move(B,C) H A,B,C
1 move(A,C) return return complete Hanoi "3,A,B,Cͤ 3.1.3 Transformation from recursion to non-recursion
Call subroutine
Call subroutine
Call subroutine
Call subroutine
recursively 45
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
H A,B,C
H A,C,B
3 2 H A,B,C
1 move(A,C) return move(A,B) H C,A,B
1 move(C,B) return Return
move(A,C) H B,A,C
2 H B,C,A
1 move(B,A) return move(B,C) H A,B,C
1 move(A,C) return ֚ Complete
Hanoi"3,A,B,Cͤ
Call subroutine
recursively Call subroutine
Call subroutine
Call subroutine
Call subroutine
Call subroutine
recursively 46
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
3,A,B,C
2,A,C,B
1,A,B,C 1,C,A,B
2,B,A,C
1,B,C,A 1,A,B,C
The status of stack when the recursion is executed 3.1.3 Transformation from recursion to non-recursion
hanoi(3,A,B,C) 㓶嫛move(A,C) 㓶嫛move(A,B) 㓶嫛move(C,B) 㓶嫛move(A,C) 㓶嫛move(B,A) 㓶嫛move(B,C) Perform move(A,C)
hanoi(2,A,C,B) hanoi(1,A,B,C) hanoi(1,C,A,B) hanoi(2,B,A,C) hanoi(1,B,C,A) hanoi(1,A,B,C) 47
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Chapter 3
Stacks and
Queues
A recursive mathematical formula 3.1.3Transformation from recursion to non-recursion