Recursion (part 1/2)#
Python Programming for Engineers#
Tel-Aviv University / 0509-1820 / Fall 2025-2026#
Agenda#
Recursion#
Lecture reminder - the Matryoska doll problem#
Recursive Pseudo code#
def how many dolls(this_doll):
if this_doll has no more dolls inside it:
return 1
else:
answer = this doll + all dolls inside it
return answer
Lecture reminder - the recursive approach#
|
Base (termination) condition |
|
Decomposition to smaller instances |
|
Use solutions of smaller instances to solve the original problem |
Power Calculation#
Natural power definition:
\(x^y = x \cdot x \cdot β¦ \cdot x\) (y times)
How can we solve it using the recursive approach?#
Power Calculation - the recursive approach#
Base case:#
\(y=0 \Longrightarrow x^0=1\)
Decomposition:#
Calculating \(x^{y-1}\): the solution for a problem which is one step closer to the base case
Aggregation:#
Assuming we have the solution for \(x^{y-1}\), we use it for our solution: \(x^y = x \cdot x^{y-1}\)
Or, Mathematically :#
\(x^y= \begin{cases} 1,& \text{if } y=0 \\ x\cdot x^{y-1},& \text{otherwise} \end{cases} \)
Python recursive implementation#
def power(x, y):
if y == 0:
return 1 # STOP
result = power(x,y-1) #DECOMPOSITION
return x * result # AGGREGATION
print(power(2,5))
32
print(power(3,3))
27
Fast Power Calculation#
Natural power definition:#
\(x^y = x \cdot x \cdot β¦ \cdot x\) (y times)
Fast Power Formula:#
\(x^y= \begin{cases} 1,& \text{if } y=0 \\ x\cdot x^{y-1},& \text{y is odd} \\ x^{y/2}\cdot x^{y/2},& \text{y is even} \end{cases} \)
Why is it fast?#
Because it requires less calculations
Example #1: \(2^{17}\)#
power(2,17)requires 17 extra function calls:power(2,16)power(2,15)β¦
power(2,0)
fast_power(2, 17)requires only 6:fast_power(2,16)fast_power(2,8)fast_power(2,4)fast_power(2,2)fast_power(2,1)fast_power(2,0)
Example #2: \(0.5^{30}\)#
power(0.5,30)requires 30 extra function calls:power(0.5,29)βpower(0.5,28)β β¦ βpower(0.5,0)
fast_power(0.5,30)requires only 9:fast_power(0.5,30)fast_power(0.5,15)fast_power(0.5,14)fast_power(0.5,7)fast_power(0.5,6)fast_power(0.5,3)fast_power(0.5,2)fast_power(0.5,1)fast_power(0.5,0)
How fast is fast calculation? What is the relation between the power and the number of multiplications?
Fast power - python recursive implementation#
def fast_power(x, y):
print('fast_power(' + str(x) + ',' + str(y) + ')-->', end=' ')
if y == 0:
return 1
if y%2 == 0: # even power
tmp = fast_power(x, y // 2)
return tmp*tmp
return x * fast_power(x, y - 1) # odd power
print(fast_power(2,5))
fast_power(2,5)--> fast_power(2,4)--> fast_power(2,2)--> fast_power(2,1)--> fast_power(2,0)--> 32
print(fast_power(0.5,17))
fast_power(0.5,17)--> fast_power(0.5,16)--> fast_power(0.5,8)--> fast_power(0.5,4)--> fast_power(0.5,2)--> fast_power(0.5,1)--> fast_power(0.5,0)--> 7.62939453125e-06
Letβs draw together the recursion tree (Try also with this tool)#
\({n \choose k}\) - Choose k elements from n#
How many different ways to choose k volunteers out of n students?
For example:#
If we have four students: (Hagai, Shimon, Omer, Amir), and we need only one volunteer, we can assemble 4 different groups of 1 volunteer:
(Hagai), (Shimon), (Omer), (Amir)
\({4 \choose 1}=4\)
If we have four students: (Hagai, Shimon, Omer, Amir), and we need two volunteers, we can assemble 6 different groups of 2 volunteers:
(Hagai, Shimon), (Hagai, Omer), (Hagai, Amir), (Shimon, Omer), (Shimon, Amir), (Omer, Amir)
\({4 \choose 2}=6\)
n choose k: the recursive approach#
We fill up our k-size volunteer group with students.
Base case (Stop criteria):
k == 0 \(\rightarrow\) return 1
Can only be one voluinteer group of size 0 - the empty group
k == n \(\rightarrow\) return 1
Can only be one volunteer group of size k - the group of all students
n < k \(\rightarrow\) return 0
There are not enough students to volunteer
n choose k: the recursive approach#
Decomposition:
We look at one student at the time, and consider two sets of possible volunteer groups:
groups with this student
where we have to choose k-1 more volunteers, from a group of n-1 students
\({n-1 \choose k-1}\)
groups without this studen
where we have to choose k more volunteers, from a group of n-1 students
\({n-1 \choose k}\)
Each of the above options, make the problem one step simpler.
Aggregation:
The above sets are disjoint, so we can sum up their results:
\({n \choose k}\)=\({n-1 \choose k-1}\)+\({n-1 \choose k}\)
n choose k: Python recursive implementation#
def choose(n, k):
if k==0 or n==k: # STOP
return 1
if n < k: # STOP
return 0
return choose(n - 1, k - 1) + choose(n - 1, k) # DECOMPOSITION + AGGREGATION
print(choose(4, 1))
4
print(choose(4, 2))
6
print(choose(20, 5))
15504
n choose k: recursion tree#
String merge#
Input: strings z,x,y
Output: is z a merge of x and y?
Examples
|
|
is_merge(π,π,π) pseudo code:#
Base:
If π₯ is empty, the answer is π§==π¦.
If y is empty, the answer is π§==π₯.
If π₯,π¦ arenβt empty but π§ is, the answer is False.
Decomposition: For all other cases, if \(z\) is a merge, its first character must be the first character of \(x\) or the first character of \(y\). So we compare and aggregate a one step simpler version:
π§[0]==π₯[0] πππ ππ _πππππ(π§[1:],π₯[1:],π¦)
ππ
π§[0]==π¦[0] πππ ππ _πππππ(π§[1:],π₯,π¦[1:])
String merge - Python implenentation#
def is_merge(z, x, y):
if len(x) == 0: # STOP
return z == y
if len(y) == 0: # STOP
return z == x
if len(z) == 0: # STOP
return False
if z[0] == x[0] and is_merge(z[1:], x[1:], y): # DECOMPOSITION + USE
return True
if z[0] == y[0] and is_merge(z[1:], x, y[1:]): # DECOMPOSITION + USE
return True
return False
x, y, z = "rrkrrrk", "rrrkrrkr", "rrrkrrrkrrrkrkr"
res=is_merge(z, x, y)
print(f'solution: {res}')
solution: True
x, y, z = ["r", "k", "z"], ["i", "c"], ["r", "i", "c", "k", "z"]
res=is_merge(z, x, y)
print(f'solution: {res}')
solution: True
Avoid duplication of sequences (list)#
Reminder: slicing duplicates the list
Note that each time th recursive function is called, a duplication of that (sliced) list is passed to the inner scope
Solution: use indices instead of slicing
Pass indices of current element as an argument of the recursion
String merge - Python implenentation (without list duplication)#
def is_merge(z, x, y, z_i=0, x_i=0, y_i=0):
if len(x) == x_i: # STOP
return z[z_i:] == y[y_i:]
if len(y) == y_i: # STOP
return z[z_i:] == x[x_i:]
if len(z) == z_i: # STOP
return False
if z[z_i] == x[x_i] and is_merge(z, x, y, z_i+1, x_i+1, y_i): # DECOMPOSITION + USE
return True
if z[z_i] == y[y_i] and is_merge(z, x, y, z_i+1, x_i, y_i+1): # DECOMPOSITION + USE
return True
return False
x, y, z = ["r", "k", "z"], ["i", "c"], ["r", "i", "c", "k", "z"]
res=is_merge(z, x, y)
print(f'solution: {res}')
solution: True
Self Learning#
what_am_i_doing#
def what_am_i_doing(num):
print(f'cur: {num}')
if num == 0 : # STOP
return 0
rightmost_digit = num % 10
rest_of_num = num // 10
x = what_am_i_doing(rest_of_num) # DECOMPOSITION
y = x + rightmost_digit # AGGREGATION
return y
print(f'result: {what_am_i_doing(137)}')
cur: 137
cur: 13
cur: 1
cur: 0
result: 11
print(f'result: {what_am_i_doing(87)}')
cur: 87
cur: 8
cur: 0
result: 15
What is it doing?#
Solution#
what_am_i_doing is a recursive program that receives an integer and returns its sum of digits
We do not know the number of digits in advance#
For example:
>>>what_am_i_doing(1204)
7
Unfolds as so:
sum_of_digits(1204) = sum_of_digits(120) + 4 = sum_of_digits(12) + 0 + 4 = sum_of_digits(1) + 2 + 0 + 4 = 1+2+0+4
A shorter implementation (avoiding temporal assignments)#
def sum_of_digits_shorter(num):
print(f'cur: {num}')
if num == 0: # STOP
return 0
return sum_of_digits_shorter(num // 10) + num % 10 # DECOMPOSITION + AGGREGATION
print(f'final result: {sum_of_digits_shorter(137)}')
cur: 137
cur: 13
cur: 1
cur: 0
final result: 11
Question from 2425b: Divisible by 9#
In this section, we will check whether a number is divisible by 9 without using the modulo (%) operator.
To do so, we will implement the function divisible_by_nine, which receives a positive integer n (of type int) and returns a Boolean value β True if the number is divisible by 9, and False otherwise.
To determine whether n is divisible by 9, we will rely on the following fact:
A number is divisible by 9 if and only if the sum of its digits is also divisible by 9.
Notes:
You may use the integer division operator (
//) and the modulo operator (%), but only to divide by 10 and to find the remainder when dividing by 10.You may assume valid input:
nis a positive integer (int).
>>> divisible_by_nine(1809)
True
>>> divisible_by_nine(111)
False
# Solution
def divisible_by_nine(n):
if n < 10:
return n == 9
# Calculate sum of digits
sum_of_digits = 0
while n != 0:
sum_of_digits += n % 10
n //= 10
return divisible_by_nine(sum_of_digits)
print(divisible_by_nine(1809))
print(divisible_by_nine(111))
True
False
The n-queens problem#
The n-queens problem is about finding how many different ways queens can be placed on a chessboard so that none attack each other
For implemetation details see here