Recursive Algorithms and Procedures

1
 Contents
• Basic concepts
– Recursion (sự đệ quy)
– Recursive algorithms (giải thuật đệ quy)
• Structure of recursive algorithms
• Operation of recursive algorithms
• Recursive procedures (thủ tục đệ quy)
– Concepts
– Structure of recursive procedure
– Operation
– Implementation principles
– Cancellation of recursion (Khử đệ quy)
• Backtracking algorithms

2
 Nội dung
• Examples of recursive algorithms
– Searching in linked lists
– Problem of Hanoi tower (Bài toán Tháp Hà Nội)
– Problem of 8 queens (Bài toán 8 con hậu)

3
 Basic concepts
• Recursion by examples:
Some recursive definitions:
– String: is defined as:
• Rule 1: 1 char = String
• Rule 2: String = 1 char + (sub) String
– Natural number: a natural number N is defined as:
• Rule 1: 1 is a natural number
• Rule 2: x is a natural number if (x-1) is a natural number
– N! = 1.2. … .N can be defined as:
• Rule 1: 0! = 1
• Rule 2: N! = N (N-1)!
– Definition of a linear list:
• Rule 1: L = empty is a linear list
• Rule 2: If Ln-1 is a linear list of n-1 length, then the construt Ln =
<a, Ln-1> which means element a is before Ln-1, is also a linear list.

4
 Basic concepts
• Recursive definition (định nghĩa đệ quy): the way
defining an object that based on other similar (usually
smaller) objects. A recursive definition includes 2 parts:
– Basic rule (Quy tắc cơ sở): also called basic case where a
special case of target object is defined directly.
– Inductive rule (Quy tắc đệ quy): where the object is defined
indirectly based on other similar objects
• Recursive property (tính chất đệ quy): an object has
recursive property if it can be defined recursively. It
means that the object contains other similar objects.

5
 Basic concepts
• Recursive algorithm (Giải thuật đệ quy)
– Exp 1: Searching for a given word w in a dictionary T
T1.1
T1 ...
T1.2
T
T2.1 ...
T2
T2.2

– Main idea of algorithm:

– T is partitioned into 2 equal sub-
dictionaries T1 and T2.
– Searching for w in T1 and T2
– The process continues until the final
sub-dictionary has only one page,
and the search can be done directly.

6
 Basic concepts
• Recursive algorithm
– Exp 2: Calculation of Fibonacci series:
• F(n) = 1 for n <= 2 (F(1) = F(2) =1);
• F(n) = F(n-1) + F(n-2) for n > 2;

7
 Basic concepts
• Recursive algorithm (Giải thuật đệ quy)
– Concept: Given a problem P, an algorithm for P is called
recursive if it has following form:
• For solving P, we need to solve problem P1 that is similar and smaller
than P. It means that if P1 is solved, than P is also solved.
• Similarly, for solving P1, we find another similar and smaller problem
P2 needs to be solved. The process continues until we find problem Pn
that is similar and smaller Pn-1.
• Pn is small enough that it can be directly solved.
• After resolving Pn, we will solve all generated problems Pn-1, Pn-2, …,
P1, and finally P.

Recursive induction (suy diễn đệ quy)

P P1 P2 … Pn-1 Pn điểm dừng

Backtracking (Quay lui)

8
 Recursive algorithm
• Exp 3: Find the minimal element of a given series with N
elements a1, a2, …, aN
• If N=1 then min=a1;
• Else the series is divided into 2 sub-series:
L1 = a1, a2,…, am and L2 = am+1, am+2,…, aN
with m = (1+N) DIV 2.
Find min1 in L1 and min2 in L2.
Compare min1 and min2 to find the minimal.

9
 Recursive algorithm
• Structure of recursive algorithm:
– Base case (Trường hợp cơ sở): the case of small enough
problem (Pn) that can be solved directly. This case plays also
role of stopping point for recursive induction.
– Recursive case (Trường hợp đệ quy): the case contains
recursive mechanism that repeat replacement of current
problem by one or many other similar sub-problems, until the
base case arrives.
• Notes: Two above cases relate closely to each other to
determine the recursive algorithm is solvabe and
stoppable.

10
 Recursive algorithm
• Operation of recursive algorithm: including two processes:
– Recursive induction (quá trình suy diễn đệ quy): by applying recursive
mechanism, the original problem will be replaced by a series of similar sub-
problems. The process finishes when the base case arrives (stopping point
of recursive induction).
– Backtracking (quá trình quay lui): reversed process of recursive induction
process, in which the series of generated sub-problems will be solved. The
process ends when the original problem is solved.
– Exp 5: Calculating 3! by applying recursive algorithm:

3! = 3 x 2!
Recursive 2! = 2 x 1! Backtracking
induction 1! = 1 x 0!
0! = 1: base case

11
 Recursive procedures
• Concepts:
– Recursive procedure: is a simple and effective tool (sub-
program) supported in most programming languages to
implement recursive algorithms.
– In C/C++ it is called recursive function.
– Recursive procedure/function: is one that contains at least one
recursive call (call to itself) in its body.

12
 Recursive procedures
• Examples
– Exp 6: Calculation of n! int Fact (int n){
• 0! = 1 if (n <= 1) return 1;
• n! = n (n-1)! else return n * Fact (n-1);
}

– Recall exp 2: Calculation of series Fibonacci

• F (1) = 1 if n <= 2; recursive calls
• F (n) = F (n-1) + F (n-2) if n > 2;

int Fibo1 (int n) {

if (n <= 2) return 1;
else return (Fibo1 (n-1) + Fibo1 (n-2));
}

13
 Recursive procedures
• Structure of recursive procedure/function: In C/C++,
a recursive function has the form:

void P(A) {
if (A==A0)
Base case
else { //recursive case
Q1();
P(A1); //recursive call
Q2();
P(A2); //recursive call
…
}
}

14
 Recursive procedures
• Structure of recursive procedure/function:
– Header of function: In header a recursive function must have at
least one parameter. Besides of normal role of input/output, a
parameter in recursive function can express the size of the
function.
– Body of function: including 2 branches that corresponds to 2
cases of the algorithm:
• Base branch (Nhánh cơ sở): containing necessary statements for
implementing the base case.
• Recursive branch (Nhánh đệ quy): containing at least one recursive call.

15
 Recursive Calls
• There are 2 types of recursive calls:
– Direct recursive call (calling to itself): the called function
contains the call.

– Indirect recursive call (Gọi gián tiếp):

Example:

void A(n) { void B(m){

... ...
B(p); A(k);
... ...
} }

16
Operation of recursive procedure
int Fact (int n){
if (n <= 1) return 1;
else return n * Fact (n-1);
}

void main(){
int n = 3;
int f = Fact(n);//operating process starts here
}

17
 Operation of recursive procedure
• Running process of a RP includes 2 stages:
– Recursive call stage (Giai đoạn gọi đệ quy):
• Starting from the first call, the recursive branch will be repeated until
the base branch arrives. In this stage, many intermediate results
generated by intermediate calls need to be saved, because they will be
used in the next stage.
• The next stage (backtracking) will be triggered automatically.
– Backtracking stage (Giai đoạn quay lui):
• In this stage, all intermediate generated calls will be run one by one, and
in reversed order.
• Problem: how intermediate calls and results can be
saved in fisrt stage (recursive call) to be processed in the
second stage (backtracking)?

18
 Operation of recursive procedure
• Implementation method:
The saving and processing of recursive calls in 2 operating stages
have following features:
– Last In, First Out (LIFO):
• The processing order of recursive calls in second stage is reversed to the
order in first stage. Therefore LIFO structure (stack) is a suitable
choice.
– Homogeneity (Tính đồng nhất):
• Structure of recursive calls are the same, so homogenous stack can be
used.
• In reality, most programming languages (including
C/C++) have already supported/implemented recursive
calls and procudures.

19
 Operation of recursive procedure
(1) Initialize Stack: S = empty;
(2) Recursive calls stage (Giai đoạn gọi đệ quy):
• In this stage, intermediate recursive calls and results will be pushed into
stack.
(3) Backtracking stage (Giai đoạn quay lui)
• Recursive calls and results saved in the stack will be popped to be
processed until the stack is empty.

20
 Operation of recursive procedure
• Exp: operation of recursive function Fact(n) with n=3
(calculation of 3!).
Recursive algorithm (recall)
3! = 3 x 2!
Recursive 2! = 2 x 1! Backtracking
induction 1! = 1 x 0!
0! = 1: base case

Operation of recursive function Fact()

Call 3!: Fact(3); Return F3 (6)

(1)
F1=1*Fact(0);
(2) F2=2*Fact(1); (3)
F3=3*Fact(2);

Stack is empty Stack Stack is empty

21
Comparison Recursive vs Non-recursive procedures
• Recursive procedures
– Advantages:
• Shorter
• Easier to understand
– Disadvantages:
• More complex
• More requirement of memory
• Stack overflow error may happen

22
 Cancellation of recursion
• Concept: cancellation of recursion (sự khử đệ quy)
means that recursive algorithm is replaced by non-
recursive algorithm, or recursive calls is replaced by
other implementation.
 Recursive calls are killed (cancelled)
• Exp 1:

int Fact (int n){ int Fact (int n){

if (n <= 1) return 1; if (n <= 1) return 1;
else return n * Fact (n-1); else {
} int x=1;
for (int i=2;i<=n;i++)
x*=i;
return x;
}
}

23
 Cancellation of recursion
• Exp 2:

int Fibo1(int n){ int Fibo2(int n) {

if (n <= 2) return 1; int i, f, f1, f2;
else f1 = 1 ;
return (Fibo1 (n-1) + f2 = 1 ;
Fibo1 (n-2)); if (n <= 2) f = 1;
} else
for (i = 3;i<=n;i++){
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
}

24
 Examples of recursive algorithms & procedures
• Exp 1: Searching in linked lists:
– Write a recursive function that search for an element k in linked list H
which points to head of the list. If found, the function returns the pointer
pointing to found element. Otherwise, it returns NULL.

PNode Search (Item k, PNode H) {

if (H == NULL) return NULL;
else
if (H->info == k) return H;
else return Search (k; H->next) ;
}

25
 Examples of recursive algorithms & procedures
• Exp 2: Problem of Hanoi tower (Bài toán Tháp Hà Nội)
– Problem: there are N disks with different sizes and 3 towers A, B and C. At
the beginning, N disks lie on each others (smaller one on top of bigger one)
at tower A. You are required to move N disks from tower A to tower B with
following conditions:
• Each time only one disk can be moved
• Bigger disk is never allowed to lie on top of smaller one.
• Only one intermediate tower C can be used

A B C
26
 Exp 2: Problem of Hanoi tower
– Some simple cases
• 1 disk: A  B
• 2 disks: A  C, A  B, C  B
– General case: movement process is follows:
1. Move N-1 disks from A to C
2. Move 1 disk from A to B
3. Move N-1 disks from C to B

A B C

27
 Exp 2: Problem of Hanoi tower
• For example with 3 disks:
• Move 2 top disks from A to C: A  B, A  C, B  C

A C B
• Move 1 bottom disk from A to B: A  B

A B C
• Move 2 disks from C to B: C  A, C  B, A  B

28
 Exp 2: Problem of Hanoi tower
• Function structure:
– Base case: N=1 disk: A  B
– Recursive case: N>1:
1. Move N-1 disks from A to C
2. Move 1 disk from A to B
3. Move N-1 disks from C to B

void TowerHN (int n, Tower A, B, C){

if (n == 1) Transfer (A, B);
else {
TowerHN (n-1, A, C, B);
TowerHN (1, A, B, C);
TowerHN (n-1, C, B, A);
}
}

29
 Backtracking Algorithms
• Ideas of backtracking algorithm (Ý tưởng giải thuật)
• Implementation methods (Cách cài đặt)

30
 Backtracking Algorithms
• Ideas of backtracking algorithm:
– Problem: given a set of N variables x1, x2,…, xN with N
corresponding value domains D1, D2,…, DN. Find a set of N
variables with suitable values that satisfies given condition K.
– Ideas of Backtracking Algorithm:
• Set vector Vi = <x1,x2,…,xi>, with i=1..N.
• We need to find vector VN satisfying condition K, with xiDi and
i=1..N.
• The algorithm includes N steps, each one aims to find one suitable
variable in vector V.

31
 Ideas of backtracking algorithm
Recursive algorithm for backtracking as follows:
• Suppose that first i steps have been done, it means that
we found Vi=<x1, x2,…, xi> satisfies K. If i=N the
algorithm finishes, it returns VN. Otherwise, next step
continues with two exclusive cases:
– If found suitable variable, means that  p  Di+1 so that
with xi+1=p then Vi+1 satisfies K, set xi+1=p. It repeats for
next step (i+1) (recursive induction).
– Otherwise, means that p  Di+1 we all have Vi+1 not
satisfied K. We have to backtrack to step i to try next suitable
value of xi (current xi is suitable). If not found and i=1, the
algorithm terminates without any suitable vector.

32
 Example of backtracking
• Problem of 8 queens (Bài toán 8 con hậu)
Find an arrangement of 8 queens on chessboard so that not any
two queens check each other. This problem can be generalized for
N queens.
• One of 92 solutions:

33
 Problem of 8 queens
• Ideas of Algorithm:
– Chessboard can be considered as an 2D array aNxN, (N=8 in
reality);
– Suppose that N queens are: h1, h2,…, hN, and queen hi will be
placed in row i, with i=1..N.
– We need to choose suitable column of each queen so that they
do not check each other.

34
 Problem of 8 queens (con't)
• The algorithm consists of N steps, each one will find a suitable
position (column) for one queen as follows:
– Suppose that at step i (first step i=1), i queens h1, h2,…, hi have been
placed in first i rows and this arrangement satisfies the condition (with 1
 i  N). If i=N the algorithm finishes and returns the result.
Otherwise it continues with next step.
– At step i+1, it finds a suitable column at row i+1 in order to put the queen
hi+1. Two cases may happen:
• If a suitable column j is found, then put queen hi+1 at that position j. Go to the
next step i+1.
• Otherwise if all N columns are not suitable, it must go back to step i and try to
find next suitable column (backtracking) of hi (recall that hi is already in a
suitable position). If no next suitable position exists for hi and i=1 then it
terminates without any solution.

35
 Backtracking Algorithms
• Implementation methods: there are 2 methods:
– Method 1: Using recursive procedures (thủ tục đệ quy)
– Method 2: Using non-recursive procedures (thủ tục không đệ
quy)

36
 Backtracking Algorithms
Implementation methods
• Method 1: Using recursive procedures
void RBacktrack(vector V, int step)
{
if (step == N) {
V is a solution;
}
else
while (exists xi in Di and V+{xi} satisfies K)
{
Di = Di \ {xi} ;
V = V+ {xi};
RBacktrack(V, step+1);
V = V \ {xi}; //prepare before backtrack
}
}

37
 Backtracking Algorithms
Implementation methods
• Method 2: Using non-recursive procedures (loops)
int NBacktrack ()
{
int i = 1;
int tong = 0; //total number of solutions
vector V =  ; //V is empty
do {
while (exists xi in Di and V+{xi} satisfies K)
{
Di = Di \ {xi} ;
V = V+ {xi};
if (i == N) {
V is a solution;
tong++;
}
else i++;
}
V = V \ {xi};
i-- ; //Backtrack
}
while (i >= 1);
return tong;
}

38
 Exercises
1. Find recursive algorithm and function that sum up a series of N
numbers.
2. Find recursive algorithm and function that look for minimal
element in a series of N numbers.
3. Write a recursive function for insertion sort algorithm.
4. (Subset sum problem): Given a series A of N numbers and a
number K, is there a group of numbers of A that sums exactly to
K?
5. (Knight's tour problem): A knight's tour is a sequence of moves
of a knight on a chessboard such that the knight visits every
square exactly once. Find a/all knight's tour (s).

39
Thank you!

40