University of Science – VNU-HCM

Faculty of Information Science

Department of Computer Science
MTH083 - Advanced Programming for Artificial Intelligence

Slot 06 – Recursion

Advisor:
Dr. Nguyễn Tiến Huy
Dr. Lê Thanh Tùng

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 1

Content

1 Introduction
2 Recursion Function
3 Examples
4 Dynamic Programming

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 2

 Introduction

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 3

 Introduction
▪ Recursion is an extremely powerful problem-solving technique
▪ Recursion is encountered not only in mathematics, but also in daily life
▪ An object is said to be recursive if it is defined in terms of a smaller
version of itself

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 4

 Introduction
▪ This technique provides a way to break complicated problems down into
simple problems which are easier to solve
▪ For example, we can define the operation "find your way home" as:
▪ If you are at home, stop moving
▪ Take one step toward home
▪ “find your way home"

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 5

 Introduction
▪ All recursive algorithms must have the following:
▪ Base Case (i.e., when to stop) - Halting Condition
▪ Work toward Base Case
▪ Recursive Call (i.e., call ourselves)

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 6

 Recursion Example
▪ Natural numbers
▪ 0 is a natural number
▪ The successor of a natural number is a natural number
▪ Fractional:
▪ 0! = 1
▪ n! = n*(n – 1)!
▪ Fibonacci numbers:
▪ F(0) = 0, F(1) = 1
▪ F(n) = F(n - 1) + F(n - 2)

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 7

 Recursion Example
▪ Fibonacci numbers:
▪ Base case:
▪ F(0) = 0, F(1) = 1

▪ Work toward base case:

▪ F(n) = F(n - 1) + F(n - 2)
▪ Recursive Call: ??

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 8

 Recursion Function

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 9

 Recursion Function
▪ In Python, we know that a function can call other functions
▪ It is even possible for the function to call itself
▪ These types of construct are termed as recursive functions

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 10

 Recursion Function
▪ If the halting condition is not well-defined, the recursion function will be
looped infinitely.

▪ We should determine the base case carefully

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 11

 Recursion Function
▪ The structure of recursive functions is typically like the following

RecursiveFunction(){
if (test for simple case){
Compute the solution without recursion
}
else{
Break the problem into subproblems of the same form
Call RecursiveFunction() on each subproblem
Reassamble the results of the subproblems
}
}
▪ The structure of recursive functions is typically like the following
Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 12
 Recursion Function
▪ 3 “must have” of a recursive algorithm
▪ Your code must have a case for all valid inputs
▪ You must have a base case with no recursive calls.
▪ When you make a recursive case, it should be to a simpler instance
and make forward progress towards the base case

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 13

 Recursion Function
▪ Example: Calculating n!
▪ Definition 1:
▪ If n = 0: 𝑛! = 1
▪ If n > 0: n! = 1 × 2 × 3 × ⋯ × 𝑛
→ Can not use recursion
▪ Definition 2:
▪ If n = 0: 𝑛! = 1
▪ If n > 0: n! = n − 1 ! × 𝑛
→ Can use recursion

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 14

 Recursion Function
▪ Example: Calculating n!
▪ Definition 2:
▪ If n = 0: 𝑛! = 1
▪ If n > 0: n! = n − 1 ! × 𝑛

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 15

Recursion Progress

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 16

 Tracing Recursion
▪ Read more:
https://codeahoy.com/learn/re
cursion/ch8/

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 17

 Advantages/Disadvantages
▪ Advantages:
▪ Recursive functions make the code look clean and elegant.
▪ A complex task can be broken down into simpler sub-problems using recursion.
▪ Sequence generation is easier with recursion than using some nested iteration.
▪ Disadvantages:
▪ Sometimes the logic behind recursion is hard to follow through.
▪ Recursive calls are expensive (inefficient) as they take up a lot of memory and
time.
▪ Recursive functions are hard to debug.

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 18

Type of Recursion

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 19

 Type of Recursion
▪ Tail Recursion: A recursive call is said to be tail-recursive if it is the last
statement to be executed inside the function

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 20

Type of Recursion

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 21

 Type of Recursion
0 𝑖𝑓 𝑛 = 0
▪ Nested Recursion ℎ 𝑛 = ቐ𝑛 𝑖𝑓 𝑛 > 4
ℎ(2 + ℎ 2𝑛 ) 𝑖𝑓 𝑛 ≤ 4

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 22

 Recursion Example

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 23

 Example 01
▪ Write a Python program to calculate the sum of a list of numbers with
recursion
▪ Input: li = [1, 2, 3, 4, 5]
▪ Output: 15

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 24

 Example 01
▪ Calculating the sum of all elements in a list of integers:

▪ Recursion definition:

▪ Base case:

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 25

 Recursion Example
▪ Calculating the sum of all elements in an array:

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 26

 Recursion Example
▪ Calculating the sum of all elements in an array:

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 27

 Example 02
▪ Verifying if the elements in an array are in ascending order

▪ The above array is in ascending order if it satisfies two conditions

▪ The first 𝑛 − 1 elements are in ascending order, and
▪
▪ If the array contains only one element (𝑎0), it must be in ascending order

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 28

 The most common error
▪ Stack Overflow: means that you've tried to make too many function calls
recursively and the memory in stack is full
▪ If you get this error, one clue would be to look to see if you have infinite
recursion
▪ This situation will cause you to exceed the size of your stack -- no
matter how large your stack is

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 29

 Recursion and Iteration
▪ While recursion is very powerful
▪ It should not be used if iteration can be used to solve the problem in a
maintainable way (i.e., if it isn’t too difficult to solve using iteration)
▪ So, think about the problem. Can loops do the trick instead of
recursion?

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 30

 Recursion and Iteration
▪ Why select iteration versus recursion
▪ Every time we call a function a stack frame is pushed onto the
program stack and a jump is made to the corresponding function
▪ This is done in addition to evaluating a control structure (such as the
conditional expression for an if statement to determine when to stop
the recursive calls
▪ With iteration all we need is to check the control structure (such as the
conditional expression for the while, do-while, or for) → effiency

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 31

 Recursion and Iteration
▪ Iteration can be used in place of recursion
▪ An iterative algorithm uses a looping construct
▪ A recursive algorithm uses a branching structure
▪ Recursive solutions are often less efficient, in terms of both time and
space, than iterative solutions
▪ Recursion can simplify the solution of a problem, often resulting in
shorter, more easily understood source code

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 32

 Exercise 03
▪ Verifying if a string is a palindrome
▪ Formally, a palindrome can be defined as follows:
▪ If a string is a palindrome, it must begin and end with the same letter.
Further, when the first and last letters are removed, the resulting string
must also be a palindrome
▪ A string of length 1 is a palindrome
▪ The empty string is a palindrome

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 33

 Exercise 04
▪ Implement binary search with recursion

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 34

 The Towers of Hanoi Puzzle
▪ Given a set of three pegs A, B, C, and 𝑛 disks, with each disk a different size
(disk 1 is the smallest, disk 𝑛 is the largest)
▪ Initially, 𝑛 disks are on peg A, in order of decreasing size from bottom to top.
▪ The goal is to move all 𝑛 disks from
peg A to peg C
▪ 2 rules:
▪ You can move 1 disk at a time.
▪ Smaller disk must be above
larger disks

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 35

The Towers of Hanoi Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 36

The Towers of Hanoi Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 37

The Towers of Hanoi Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 38

The Towers of Hanoi Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 39

Hanoi Tower
Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 40

Hanoi Tower
Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 41

 The Towers of Hanoi Puzzle
Move n discs from peg1 to peg3 using peg2 as an auxiliary peg
if (n > 0) then
▪ Move n - 1 discs from peg1 to peg2 using peg3 as an auxiliary peg
▪ Move the remaining disc from peg1 to peg3
▪ Move n - 1 discs from peg2 to peg3 using peg1 as an auxiliary peg

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 42

The Towers of Hanoi Puzzle

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 43

 Exercise 05
▪ Find the sum of all digits in the positive number n
▪ Input: n = 1243
▪ Output: 10

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 44

 Exercise 06
▪ Find the biggest digit in the positive number n
▪ Input: n = 1243
▪ Output: 4

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 45

 Exercise 07
▪ Check whether a positive number is a prime number of not without using
iteration

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 46

 Example:
Permutation & Combination
▪ A permutation of a set is a specific ordering of all elements in the set
▪ For example, the set {A, B, C} has six permutations:
▪ ABC, ACB, BAC, BCA, CAB, and CBA
▪ permutations without repetition, permutations without replacement

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 47

 Example:
Permutation & Combination
▪ A combination is a selection of elements of a set
▪ More formally, a k-combination is a subset of k elements from a set
▪ Unlike permutations, combinations don’t have an ordering
▪ For example, the 2-combinations of the set {A, B, C} are
▪ {A, B}, {A, C}, and {B, C}:
▪ The term “n choose k” refers to the number of possible combinations
(without repetition) of k elements that can be selected from a set of n
elements

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 48

 Example: Permutation
▪ Now, consider the basic problem as “generating all permutation of each
element in the set”
▪ Input: a string of characters
▪ Return: an array of strings of every possible permutation of those
characters

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 49

 Example: Permutation
▪ What argument is passed to the recursive function call?
▪ The string argument missing one character
▪ A separate recursive call is made for each character missing
▪ How does this argument become closer to the base case?
▪ The size of the string shrinks
▪ eventually becomes a single-character string
▪ What is the base case?

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 50

 Example: Permutation
▪ Consider from the simple case to harder one:
▪ S = [] ==> result = []
▪ S = ['A'] ==> result = ['A']
▪ S = ['A', 'B'] ==> put 'A' in all places of [‘B’]

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 51

 Example: Permutation
▪ Consider from the simple case to harder one:
▪ S = [] ==> result = []
▪ S = ['A'] ==> result = ['A']
▪ S = ['A', 'B'] ==> put 'A' in all places of ['B’]

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 52

 Example: Permutation
▪ Consider from the simple case to harder one:
▪ find Permutation ['A', 'B', 'C']
==> find Permutation ['B', 'C']
==> find Permutation ['C'] ==> return ['C']
==> put 'B' in all places of ['C'] ==> ['BC','CB']
==> put 'A' in all places of ['BC','CB']
==> ['ABC', 'BAC', 'BCA', 'CBA', 'CAB', 'CBA']

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 53

Example: Permutation
def permuteList(li) -> list:
if len(li) == 1:
return li
permutation = []
for per in permuteList(li[1:]):
for pos in range(len(per) + 1):
tup = per[:pos] + li[0] + per[pos:]
print(tup)
permutation.append(tup)
return permutation

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 54

 Example: Combination
▪ Now, consider the basic problem as “generating all combination of each
element in the set”
▪ Input: a string of characters
▪ Return: an array of strings of every possible combination of those
characters

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 55

Example: Combination

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 56

Example: Combination
def combination(li) -> list:
if (len(li) == 0): return [[]]
result = []
combo = combination(li[1:])
for c in combo:
result.extend([c, [li[0]] + c])
return result

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 57

Example: Combination
def combination(li) -> list:
if (len(li) == 0): return [[]]
result = []
combo = combination(li[1:])
for c in combo:
result.extend([c, [li[0]] + c])
return result

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 58

Exercise 08
1. Write a function to check whether a number is divisible
by 7 or not without using an iteration
2. Let’s consider a list of positive numbers, write a
program to check whether the combination of numbers with
either addition or subtraction is equal to the given
value V.

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 59

 The Knapsack problem
▪ Problem statement:
▪ A thief is robbing a museum and he only has a single knapsack to
carry all the items he steals.
▪ The knapsack has a capacity for the amount of weight it can hold. Each
item in the museum has a weight and a value associated with it

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 60

The Knapsack problem – variantion

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 61

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 62

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 63

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 64

0/1 Knapsack problem
def knapsack_recursive(capacity, weights, values, n):
# Base case: No items left or no capacity left in the knapsack
if n == 0 or capacity == 0:
return 0

# If the weight of the nth item is more than the knapsack capacity,
# the item cannot be included in the optimal solution
if weights[n-1] > capacity:
return knapsack_recursive(capacity, weights, values, n-1)

# Return the maximum of two cases:

# (1) nth item included
# (2) not included
else:
return max(values[n-1] +
knapsack_recursive(capacity - weights[n-1], weights, values, n-1),
knapsack_recursive(capacity, weights, values, n-1))

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 65

 Dynamic Programming

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 66

 Dynamic Programming
▪ Dynamic Programming is an algorithm design technique for
optimization problems (minimize/maximize)
▪ DP can be used when the solution to a problem may be viewed as the
result of a sequence of decisions
▪ DP reduces computation by
▪ Solving subproblems in a bottom-up fashion.
▪ Storing solution to a subproblem the first time it is solved.
▪ Looking up the solution when subproblem is encountered again
▪ Key: determine structure of optimal solutions

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 67

 Dynamic Programming
▪ Define the problem and identify its optimal structure
▪ Optimal structure: the optimal solution to the problem can be
obtained by combining the optimal solutions to its subproblems
▪ Formulate a recursive solution (top-down)
▪ Compute the value of an optimal solution in a bottom-up fashion
▪ Memorize the recursive solutions by storing the results of previous
computation in a table.
▪ Convert the recursive solution to an iterative one

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 68

Example

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 69

 Example
▪ Why is the top-down so inefficient?
▪ Recomputes many sub-problems.
▪ How many times is F(n-5) computed?

▪ We can enhance this problem by storing solution to the sub-problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 70
Example

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 71

Example

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 72

 The Knapsack problem
▪ Problem statement:
▪ A thief is robbing a museum and he only has a single knapsack to
carry all the items he steals.
▪ The knapsack has a capacity for the amount of weight it can hold. Each
item in the museum has a weight and a value associated with it

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 73

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 74

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 75

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 76

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 77

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 78

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 79

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 80

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 81

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 82

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 83

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 84

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 85

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 86

0/1 Knapsack problem

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 87

0/1 Knapsack problem
def knapsack_dp(weights, values, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]

# Build table dp[][] in a bottom-up manner

for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]],
dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 88

0/1 Knapsack problem
# Find out which items are included
items_selected = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i-1][w]:
items_selected.append(i-1)
w -= weights[i-1]

items_selected.reverse()
return dp[n][capacity], items_selected

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 89

 THANK YOU
for YOUR ATTENTION

Dr. LE Thanh Tung CSC10002 – Programming Techniques Page 90