Introduction to Programming
Module 7
Jasper Veltman
[Link]@[Link]
Department of Computer Science
Vrije Universiteit Amsterdam
November 2024
Outline
1 Simple recursion
2 Towers of Hanoi
3 Coin combinations
4 Backtracking
5 Eight queens puzzle
Module 7 2 / 38
Outline
1 Simple recursion
2 Towers of Hanoi
3 Coin combinations
4 Backtracking
5 Eight queens puzzle
Module 7 - Simple recursion 3 / 38
Recursion
▶ A function that (directly or indirectly) calls itself is called recursive
▶ Examples:
def print_stars():
print("*")
print_stars()
def print_stars():
print_stars()
print("*")
▶ Questions:
▶ how many stars will be printed by these examples?
▶ how can we stop a recursive function after a predefined number of iterations?
Module 7 - Simple recursion 4 / 38
Designing a recursive function
1 Find a stop condition:
▶ under the stop condition, recursion is not needed to solve the problem
▶ this is called the base case
2 Find the recursive call:
▶ reduce the problem a step closer towards the base case
▶ this is called the recursive step
def print_stars(n):
if n <= 0: # stop condition: if we want to print 0 stars
return # then do nothing
print("*")
print_stars(n - 1)
Module 7 - Simple recursion 5 / 38
Stop condition
▶ Usually an if-statement combined with a return statement
▶ Always before the recursive call:
▶ otherwise recursion is infinite
▶ Always in the simplest case:
▶ otherwise recursive function will not work in all situations
Module 7 - Simple recursion 6 / 38
Question
▶ Will the following code always work correctly?
def print_stars(n):
if n == 1:
print("*")
return
print("*")
print_stars(n - 1)
▶ Answer: no, the stop condition is not in the simplest case
▶ consider print_stars(0): infinite recursion
Module 7 - Simple recursion 7 / 38
Recursion is repetitive
▶ Recursion is repetitive:
▶ the same code is executed after each recursive call
▶ can be used to replace iterative solutions (for- and while-loops)
▶ Use recursion when a problem has a recursive nature:
▶ recursive problems can be reduced to a base case
▶ recursive problems are often difficult to visualize iteratively
▶ Iterative solutions are often the better option (easier to read)
▶ Some problems have elegant recursive solutions
Module 7 - Simple recursion 8 / 38
Recursive programming
▶ When programming a recursive function:
1 think of the stop condition, and make the function work in the base case
2 make the function work for the step ”above” the base case, using recursion
3 if necesarry, make the function work for all steps above the base case
Module 7 - Simple recursion 9 / 38
Example
▶ Write a recursive function def factorial(n):
(
1 if n = 0
n! =
n × (n − 1)! if n > 0
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
Module 7 - Simple recursion 10 / 38
Exercise
Exercise
Write a recursive function power(base, exponent) that calculates base to the power
exponent, with exponent being an int >= 0. You are not allowed to use the ** operator.
Module 7 - Simple recursion 11 / 38
Exercise
Exercise
Write a recursive function number_of_digits(n) that returns the amount of digits in the
number n:
▶ number_of_digits(7) == 1
▶ number_of_digits(1234) == 4
▶ number_of_digits(837451) == 6
With n being an int >= 0. You are not allowed to use the str() or len() functions.
Module 7 - Simple recursion 12 / 38
GCD
▶ The greatest common divisor (GCD) of two numbers is the largest number that both
numbers are disible by:
▶ gcd( 6, 12) == 6
▶ gcd(15, 20) == 5
▶ gcd( 9, 12) == 3
Module 7 - Simple recursion 13 / 38
Euclidean algorithm
▶ An algorithm for calculating the GCD of two numbers a and b:
▶ if a is divisible by b:
▶ b is the GCD
▶ otherwise:
▶ a gets the value of b
▶ b gets the value of a mod b
▶ repeat this algorithm
Module 7 - Simple recursion 14 / 38
Example
▶ Write a recursive function def gcd(a, b), that returns the GCD of the a and b:
def gcd(a, b):
if a % b == 0:
return b
return gcd(b, a % b)
Module 7 - Simple recursion 15 / 38
Exercise
Exercise
Consider the row of Fibonacci numbers (0 1 1 2 3 5 8 13 21 34...). The zeroth Fibonacci
number is 0, the first Fibonacci number is 1, and all following Fibonacci numbers are the
sum of their two predecessors.
Write a recursive function fibonacci(n), that returns the nth Fibonacci number.
Module 7 - Simple recursion 16 / 38
Outline
1 Simple recursion
2 Towers of Hanoi
3 Coin combinations
4 Backtracking
5 Eight queens puzzle
Module 7 - Towers of Hanoi 17 / 38
Description
▶ Towers of Hanoi is a mathematical puzzle
▶ 3 rods → one rod contains a stack of discs
▶ Objective is the move the stack to another rod
▶ Rules:
▶ only one disc can be moved at a time
▶ only the top disc of a rod can be moved
▶ a disc can never be placed on a smaller disc
Module 7 - Towers of Hanoi 18 / 38
Example
▶ Move the top disc from copper to gold
▶ Move the top disc from copper to silver
▶ Move the top disc from gold to silver
▶ Move the top disc from copper to gold
▶ Move the top disc from silver to copper
▶ Move the top disc from silver to gold
▶ Move the top disc from copper to gold
Module 7 - Towers of Hanoi 19 / 38
Problem
Problem
Write a program that prints a solution to the problem, for any given number of discs.
Module 7 - Towers of Hanoi 20 / 38
Intuition
▶ Rods can be represented by ints
▶ Write a function that can print instructions for a single move
COPPER = 1
SILVER = 2
GOLD = 3
def name(rod):
if rod == COPPER:
return "copper"
elif rod == SILVER:
return "silver"
else:
return "gold"
def print_instruction(from, to):
print("Move the top disc from %s to %s" % (name(from), name(to)))
Module 7 - Towers of Hanoi 21 / 38
Intuition
▶ n is the amount of discs that need to be moved
▶ Stop condition:
▶ n == 1: move single disc to its final position
▶ Recursive step:
▶ move n - 1 discs to a temporary rod (recursion)
▶ move the last disc to the desired rod
▶ move the other n - 1 discs to their desired position (recursion)
▶ Function parameters:
▶ number of discs that need to be moved (n)
▶ start rod, temporary rod, and end rod
Module 7 - Towers of Hanoi 22 / 38
Solution
Solution
def move(n, start, temporary, end):
if n == 1:
print_instruction(start, end)
return
move(n - 1, start, end, temporary)
print_instruction(start, end)
move(n - 1, temporary, start, end)
move(3, COPPER, SILVER, GOLD)
Module 7 - Towers of Hanoi 23 / 38
Outline
1 Simple recursion
2 Towers of Hanoi
3 Coin combinations
4 Backtracking
5 Eight queens puzzle
Module 7 - Coin combinations 24 / 38
Description
▶ Coins can be combined in multiple ways to make the same amount
▶ For instance: 0,07 Euro can be paid using the following combinations:
1 1 × 0, 05 + 1 × 0, 02
2 1 × 0, 05 + 2 × 0, 01
3 3 × 0, 02 + 1 × 0, 01
4 2 × 0, 02 + 3 × 0, 01
5 1 × 0, 02 + 5 × 0, 01
6 7 × 0, 01
Module 7 - Coin combinations 25 / 38
Problem
Problem
Write a program that calculates how many different combinations of Euro coins can be
used to pay some amount.
Module 7 - Coin combinations 26 / 38
Intuition
COIN_VALUES = [1, 2, 5, 10, 20, 50, 100, 200]
▶ The coin values can be represented as an int array
▶ program the recursive call such that each time less coin values can be used
▶ Stop condition:
▶ there is only 1 way to pay any amount using only 1-cent coins
▶ Recursive step:
▶ try to subtract each possible number times the value of the largest coin not yet
used from the amount to be paid
▶ for each of those subtractions, make a recursive call using the smaller amount
to be paid in which that largest coin can no longer be used
Module 7 - Coin combinations 27 / 38
Solution
Solution
def combinations(amount, number_of_coins):
if number_of_coins == 1:
return 1
result = 0
coin = COIN_VALUES[number_of_coins - 1]
for i in range(0, amount // coin + 1):
result += combinations(amount - i * coin, number_of_coins - 1)
return result
Module 7 - Coin combinations 28 / 38
Outline
1 Simple recursion
2 Towers of Hanoi
3 Coin combinations
4 Backtracking
5 Eight queens puzzle
Module 7 - Backtracking 29 / 38
Description
▶ Backtracking is a recursive algorithm that finds solutions for problems that have
many possible next steps from any position:
▶ incrementally find all candidate solutions
▶ abandon a candidate solution when it turns out to be invalid
▶ Recursive calls are combined to come up with the desired solution
Module 7 - Backtracking 30 / 38
Example
Find the shortest path from the start to the finish
Module 7 - Backtracking 31 / 38
Maze backtracking
1 Try all options:
▶ up
▶ right
▶ down
▶ left
2 If an option is possible (not a wall or previously visited location):
1 change state (mark the location as visited)
2 recursion step (find a path to the finish from the new location)
3 restore state (unmark the location)
Module 7 - Backtracking 32 / 38
General backtracking
for <all options from current position>:
if <option is allowed>:
<change state>
<recursion>
<restore state>
Module 7 - Backtracking 33 / 38
Outline
1 Simple recursion
2 Towers of Hanoi
3 Coin combinations
4 Backtracking
5 Eight queens puzzle
Module 7 - Eight queens puzzle 34 / 38
Description
▶ Place 8 queens on an 8 × 8 chessboard so that no two queens threaten each other
▶ this means that no two queens can be in the same row, column, or diagonal
Module 7 - Eight queens puzzle 35 / 38
Board
▶ Assume a class ChessBoard exists that represents a chess board:
class ChessBoard:
NUMBER_OF_ROWS = 8
NUMBER_OF_COLUMNS = 8
def __init__(self): ...
def place_queen(self, row, column): ...
def remove_queen(self, row, column): ...
def is_threatened(self, row, column): ...
Module 7 - Eight queens puzzle 36 / 38
Exercise
▶ Write a recursive function def place(n, board), that places n queens on a chess
board board
▶ Assume there exists a function def show(board), that displays a chess board
Module 7 - Eight queens puzzle 37 / 38
Solution
Solution
def place(n, board):
if n == 0:
show(board)
return
for column in range(1, ChessBoard.NUMBER_OF_COLUMNS + 1):
if !board.is_threatened(n, column)):
board.place_queen(n, column)
place(n - 1, board)
board.remove_queen(n, column)
Module 7 - Eight queens puzzle 38 / 38