Database Systems:
Design, Implementation, and
Management
14th Edition
Chapter 1
Database Systems
08/05/2025 Data Structures and Algorithms in Python
National Economics University
Faculty of Mathematical Economics
EP03.TITH1121 - DATA STRUCTURES AND
ALGORITHMS: Recursion and Backtracking
Instructor: Duc Minh Vu (MFE)
Email: minhvd [at] neu.edu.vn
08/05/2025 Data Structures and Algorithms in Python 2
Learning Objectives
1. Measure the performance of an algorithm by obtaining running times and
instruction counts with different data sets
2. Analyze an algorithm’s performance by determining its order of
complexity, using big-O notation
3. Distinguish the common orders of complexity and the algorithmic
patterns that exhibit them
08/05/2025 Data Structures and Algorithms in Python 3
Learning Objectives
After completing this chapter, you will be able to:
1. Distinguish between the improvements obtained by tweaking an
algorithm and reducing its order of complexity
2. Write a simple linear search algorithm and a simple sort algorithm
08/05/2025 Data Structures and Algorithms in Python 4
2.2 What is Recursion?
Any function which calls itself is called recursive.
A recursive method solves a problem by calling a copy of itself to work on
a smaller problem.
Recursion step.
Recursion step can result in many more such recursive calls
08/05/2025 Data Structures and Algorithms in Python 5
2.3 Why Recursion?
A useful problem solving technique borrowed from mathematics.
Shorter and easier to write than iterative code.
Useful for tasks that can be defined in terms of similar subtasks.
Sort, search, and traversal problems often have simple recursive solutions.
08/05/2025 Data Structures and Algorithms in Python 6
2.4 Format of a Recursive Function
1. Base cases: These tell the recursion when to terminate,
meaning the recursion will be stopped once the base condition is
met
2. Recursive cases: The function calls itself recursively, and we
progress toward achieving the base criteria
08/05/2025 Data Structures and Algorithms in Python 7
Factorial
n! is the product of all integers between n and 1. The definition of
recursive factorial looks like:
n! = 1 if n = 0
n! = n * (n-1)! if n > 0
08/05/2025 Data Structures and Algorithms in Python 8
08/05/2025 Data Structures and Algorithms in Python 9
2.6 Recursion versus Iteration
Recursion
Terminates when a base case is reached.
Each recursive call requires extra space on the stack frame (memory).
If we get infinite recursion, the program may run out of memory and result in stack overflow.
Solutions to some problems are easier to formulate recursively.
Iteration
Terminates when a condition is proven to be false.
Each iteration does not require extra space.
An infinite loop could loop forever since there is no extra memory being created.
Iterative solutions to a problem may not always be as obvious as a recursive solution.
08/05/2025 Data Structures and Algorithms in Python 10
2.8 Example Algorithms of Recursion
Fibonacci series, factorial finding
Merge sort, quick sort
Binary search
Tree traversals and many tree problems: InOrder, PreOrder PostOrder
Graph traversals: DFS [Depth First Search]
Dynamic programming examples
Divide and conquer algorithms
Towers of Hanoi
Backtracking algorithms [we will discuss in next section]
08/05/2025 Data Structures and Algorithms in Python 11
2.9 Recursion: Problems & Solutions
Tower of Hanoi - Wikipedia
It consists of three rods (or pegs or towers) and a number of disks of
different sizes which can slide onto any rod.
The puzzle starts with the disks on one rod in ascending order of size, the
smallest at the top.
The objective of the puzzle is to move the entire stack to another rod,
satisfying the following rules:
Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the rods and sliding it onto another
rod, on top of the other disks that may already be present on that rod.
No disk may be placed onData
topStructures
of a smaller
and Algorithmsdisk.
08/05/2025 in Python 12
Tower of Hanoi
Algorithm:
1. Move m − 1 disks from the source to the spare peg, by the same general solving
procedure.
2. Move the disk m from the source to the target peg.
3. Move the m − 1 disks from the spare to the target peg by the same general solving
procedure
4. The base case is to move 0 disks (in steps 1 and 3), that is, do nothing—which obviously
does not violate the rules
08/05/2025 Data Structures and Algorithms in Python 13
08/05/2025 Data Structures and Algorithms in Python 14
Check whether the array is in sorted order with recursion.
08/05/2025 Data Structures and Algorithms in Python 15
Summing the Elements of a Sequence Recursively
08/05/2025 Data Structures and Algorithms in Python 16
O(n) time
O(n) memory
08/05/2025 Data Structures and Algorithms in Python 17
Summing the Elements of a Sequence Recursively
08/05/2025 Data Structures and Algorithms in Python 18
O(n) time
O(logn) memory
08/05/2025 Data Structures and Algorithms in Python 19
Reversing a Sequence with Recursion
08/05/2025 Data Structures and Algorithms in Python 20
O(n) time
O(n) memory
08/05/2025 Data Structures and Algorithms in Python 21
Recursive Algorithms for Computing Powers
O(n) time
O(n) memory
08/05/2025 Data Structures and Algorithms in Python 22
O(logn) time
O(logn) memory
08/05/2025 Data Structures and Algorithms in Python 23
Divide and Conquer Algorithms
08/05/2025 Data Structures and Algorithms in Python 24
Divide and conquer algorithm
An important algorithm design technique based on recursion.
Works by recursively breaking down a problem into two or more sub
problems of the same type, until they become simple enough to be solved
directly.
The solutions to the sub problems are then combined to give a solution to
the original problem
08/05/2025 Data Structures and Algorithms in Python 25
18.2 What is Divide and Conquer Strategy?
The D & C strategy solves a problem by:
1. Divide: Breaking the problem into subproblems that are themselves
smaller instances of the same type of problem.
2. Conquer: Conquer the subproblems by solving them recursively.
3. Combine: Combine the solutions to the subproblems into the solution
for the original given problem.
08/05/2025 Data Structures and Algorithms in Python 26
08/05/2025 Data Structures and Algorithms in Python 27
