Recursion 1 - Simple functional programming
In the past, you looped with for
and while
cycles: everything was so easy back then.
Today you’re gonna try a new thing called recursion.
References:
Functional programming paradigm heavily relies upon recursion and is becoming quite popular (you will probably need using it during the master), so let’s gain some basic understanding of its principles.
In a purely functional programming paradigm:
functions behave as mathematical ones: they always take some parameter and always return NEW data or pointers to (parts of) original input, without ever changing it
variables can be assigned only once
all looping is done via recursion
side effects are not allowed (will talk more about them later)
Python was not designed to fully support functional programming, so if we adhere to its strictest principles we will end up with inefficient code. Why whould we bother, then? The bright side is that by limiting what we can do we can focus on the logic of recursion, without caring about performance issues (we will deal with them later).
So first you will try to develop some functions in SimpleFP, a purely functional programming style we just invented for these worksheets.
SimpleFP - how-to
In this section we ask you to devise algorithms in which you:
never mutate data
always RETURN NEW data or pointers to (part of) input
assign variables only once
always return from each branch of functions
never use side-effects inside functions: a side-effect is something that is independent from function parameters and/or modifies the environment without storing reusable values in memory. Examples:
getting the current time or interactively asking
input
from the user implies a different result at each executioncalling
print
only illuminates pixels on the screen without storing resuable values in memory.
Your code is allowed to:
be inefficient, both in memory and execution time
hit recursion stack limits imposed by Python: since we will only test with small data in practice this shouldn’t happen anyway
SimpleFP - variable assignment
Assign variables only once.
Avoid:
[2]:
x = 3
x = x + 1 # don't
Instead, feel free to create new variables at will:
[3]:
x = 3
y = x + 1 # ok
SimpleFP - list creation
To create new list, use boxing, concatenation or slicing.
SimpleFP - boxing
wrap one or more objects with
[
,]
[4]:
la = ['a'] # list of one element
lb = ['a','b','c'] # list of n elements
SimpleFP - concatenation
To join two lists only use +
operator, which creates a NEW list.
Avoid methods which modify lists:
[5]:
lst = ['a','b']
lst.append('c') # don't, it's mutating lst
lst.append('d')
lst.extend(['c','d']) # don't, it's mutating lst
Instead, do:
[6]:
la = ['a','b']
lb = la + ['c','d'] # '+' creates a NEW list without modifying the operands
# here also reassigns to a NEW variable
lc = la + ['e'] # if you need to add only one element just wrap it in square brackets
SimpleFP - accessing list elements
You can take an element at any position
[7]:
lst = [5,2,8,7,1,3]
[8]:
lst[0]
[8]:
5
[9]:
lst[4]
[9]:
1
SimpleFP - slicing
To take sublists in this purely functional model we allow slicing, even if on Python lists it’s quite inefficient as it creates entirely NEW lists.
DO NOT use stepping
[10]:
lst = ['a','b','c','d','e','f','g','h','i']
lst[1:]
[10]:
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
[11]:
lst[len(lst)//2:]
[11]:
['e', 'f', 'g', 'h', 'i']
[12]:
lst[:len(lst)//2]
[12]:
['a', 'b', 'c', 'd']
[13]:
lst[0:5:2] # don't use stepping
[13]:
['a', 'c', 'e']
QUESTION: If we used numpy arrays, would we waste memory when slicing?
Show answerSimpleFP - minimal instruction set
To force you using recursion, we require these restrictions:
ONLY USE:
list concatenation with
+
getting length with
len(lst)
in
operator on dictionaries or sets
DO NOT use in
operator in sequences like strings, lists, tuples
DO NOT use *
replication operator on lists
DO NOT use predefined functions (sum
, max
, min
, range
, ….)
DO NOT use methods!
[14]:
5 in [3,5,2,6] # don't
[7,5,6,9] * 3 # don't
sum([5,2,7,4]) # don't
[3,5,2,5,4].count(5) # don't
[3,4] + [9,2,3] # ok
len([3,5,1,6]) # ok
'a' in {'a':4, # ok
'b':9}
SimpleFP - functions and conditionals
In purely functional programming we want of course… functions: we require they always get some input and always RETURN NEW data taken from (parts of) the input
Avoid:
[15]:
x = 4
def inc(): # bad, takes no explicit input ....
return x + 1
def app(lst):
lst.append('a') # bad, modifies input
def srt(lst):
lst.sort() # bad, modifies input
Instead, do:
[16]:
def inc(x): # ok, uses only input
return x + 3
def app(lst):
return lst + ['a'] # ok, creates a NEW list
def srt(lst):
return sorted(lst) # ok, creates a NEW list
# (note sorted must be explicitly allowed by text)
SimpleFP - recursion
In a purely functional model we don’t use loops at all! Instead, we prefer recursive calls.
Always remember:
at least one base case
always return in each branch
at least one recursive call on smaller parts of the input
always return the proper type (you might need boxing)
DO NOT use for
, while
nor list comprehensions
Simple FP - Example - scount
Suppose given a number n
, you want to build a list with first numbers from 1
to n
without using range
[17]:
def scount(n):
if n <= 0:
return []
else:
return scount(n - 1) + [n]
scount(3)
jupman.pytut()
[17]:
Simple FP - debugging
To debug you can and should of course use Python tutor.
Another trick could be to pass an additional optional parameter called level
and do some indented print
like so:
IMPORTANT: print
is ONLY for debugging!
print
by definition illuminates the pixels on your screen and doesn’t produce any reusable value in memory. So your functions are still required to always RETURN proper values!
[19]:
def scount(n, level=0):
print(' ' * level, 'n=', n)
if n <= 0:
return []
else:
return scount(n - 1, level + 1) + [n]
scount(3)
n= 3
n= 2
n= 1
n= 0
[19]:
[1, 2, 3]
Decomposing computation: Furthermore, you can try separate the steps in smaller parts and print intermediate results. Here we added the extra variable res
and printed it after the recursive call:
[21]:
def scount(n, level=0):
print(' ' * level, 'n=', n)
if n <= 0:
return []
else:
res = scount(n - 1, level + 1)
print(' ' * level, 'res=', res)
return res + [n]
scount(5)
n= 5
n= 4
n= 3
n= 2
n= 1
n= 0
res= []
res= [1]
res= [1, 2]
res= [1, 2, 3]
res= [1, 2, 3, 4]
[21]:
[1, 2, 3, 4, 5]
SimpleFP: a recursion scheme
Suppose we now want to get a list as input and return another one.
For this first section, we will follow a simple scheme:
check sequence length
if base case, immediately return something
otherwise, do recursion on the rest of the sequence
combine recursion result in some way with first element
return the combination result
Example - sdouble
Let’s see how to write a function which takes a lst
of numbers and RETURN a NEW list with the numbers doubled. You might write stuff like this:
[23]:
def sdouble(lst):
if len(lst) == 0:
return [] # base case
else:
return [lst[0]*2] + sdouble(lst[1:]) # returning operation containing
# a recursive call on a smaller input
result = sdouble([7,9,5])
jupman.pytut()
[23]:
Exercise - debug double
Try placing extra debug prints and separating the steps in the code above
Show solution[25]:
result = sdouble([4,9,1,5,7,3])
result
lst= [4, 9, 1, 5, 7, 3]
lst= [9, 1, 5, 7, 3]
lst= [1, 5, 7, 3]
lst= [5, 7, 3]
lst= [7, 3]
lst= [3]
lst= []
res= []
res= [6]
res= [14, 6]
res= [10, 14, 6]
res= [2, 10, 14, 6]
res= [18, 2, 10, 14, 6]
[25]:
[8, 18, 2, 10, 14, 6]
Exercise - sfilter_even
Takes a lst
of numbers, and RETURN a NEW list with only the even numbers
[27]:
def sfilter_even(lst):
raise Exception('TODO IMPLEMENT ME !')
result = sfilter_even([3,7,10,5,4,8,6,11])
print(result) # [10, 4, 8, 6]
assert sfilter_even([3]) == []
assert sfilter_even([4]) == [4]
assert sfilter_even([3,6]) == [6]
assert sfilter_even([8,3]) == [8]
assert sfilter_even([8,3,2]) == [8,2]
assert sfilter_even([7,7,8,3,2]) == [8,2]
assert sfilter_even([3,7,10,5,4,8,6,11]) == [10,4,8,6]
Exercise - smerry
Given a lst
with an even number of elements, RETURN a NEW list holding two element lists with consecutive content taken from the original list.
[28]:
def smerry(lst):
raise Exception('TODO IMPLEMENT ME !')
result = smerry(['a','b','c','c','a','d','b','a'])
print(result) # [['a','b'],['c','c'],['a','d'],['b','a']]
assert smerry([]) == []
assert smerry(['d','b']) == [['d','b']]
assert smerry(['a','a','b','b']) == [['a','a'],['b','b']]
assert smerry(['a','b','c','d']) == [['a','b'],['c','d']]
assert smerry(['a','b','c','c','a','d','b','a']) == [['a','b'],['c','c'],['a','d'],['b','a']]
Exercise - ssum
Takes a lst
of numbers and RETURN the sum of all numbers.
DO NOT use sum
function ;-)
[29]:
def ssum(lst):
raise Exception('TODO IMPLEMENT ME !')
result = ssum([4,2,6,3])
print(result) # 15
assert ssum([4,2,6,3]) == 15
assert ssum([]) == 0
assert ssum([3]) == 3
assert ssum([5,1]) == 6
Exercise - smin
Given a lst
of numbers, RETURN the minimum
DON’T use
min
function..assume the list has at least one element
[30]:
import math
def smin(lst):
raise Exception('TODO IMPLEMENT ME !')
result = smin([3,6,5,8,-3,8,-2,-10,4])
print(result) # -10
assert smin([4]) == 4
assert smin([4,1]) == 1
assert smin([0,9]) == 0
assert smin([6,8,5]) == 5
assert smin([3,6,5,8,3,8,2,10,4]) == 2
Exercise - ssearch
Given an el
to search and a lst
, RETURN True
if such element is present or False
otherwise
DO NOT use
in
operator nor search methods like.find
,.index
, ….consider shortening your code by using Boolean evaluation order
[31]:
def ssearch(el, lst):
raise Exception('TODO IMPLEMENT ME !')
print(ssearch(7, [6,4,7,8])) # True
print(ssearch(5, [6,4,7,8])) # False
assert ssearch(7, [6,4,7,8]) == True
assert ssearch(7, [8]) == False
assert ssearch(8, [8]) == True
assert ssearch(5, [8,5]) == True
assert ssearch(2, [8,5]) == False
assert ssearch(7, [7,8,5]) == True
assert ssearch(2, [8,2,5]) == True
assert ssearch(9, [7,8,9]) == True
assert ssearch(2, [8,9,5]) == False
Exercise - sbin_search
If the list is already sorted we can write a faster search. Start looking in the middle of the list: if that cell is the searched element, you’re done. Otherwise if searched element is lesser do recursion on left sublist, otherwise on right sublist.
lst
is a list of \(n\) already sorted elements
DO NOT use in
operator, .find
nor .index
methods
[32]:
def sbin_search(el, lst):
raise Exception('TODO IMPLEMENT ME !')
print(sbin_search(33, [8,9,15,17,20,24,28,29,33,36,39])) # True
print(sbin_search(10, [8,9,15,17,20,24,28,29,33,36,39])) # False
assert sbin_search(5, [5]) == True
assert sbin_search(4, []) == False
assert sbin_search(3, [7]) == False
assert sbin_search(3, [3,7]) == True
assert sbin_search(3, [3,6]) == True
assert sbin_search(4, [2,9]) == False
assert sbin_search(5, [2,9]) == False
assert sbin_search(5, [5,7,9]) == True
assert sbin_search(7, [5,7,9]) == True
assert sbin_search(9, [5,7,9]) == True
assert sbin_search(4, [5,7,9]) == False
assert sbin_search(6, [5,7,9]) == False
assert sbin_search(8, [5,7,9]) == False
assert sbin_search(10, [5,7,9]) == False
assert sbin_search(33, [8,9,15,17,20,24,28,29,33,36,39]) == True
assert sbin_search(10, [8,9,15,17,20,24,28,29,33,36,39]) == False
Exercise - szip
Given two lists, RETURN a NEW list having couples as tuples with elements taken pairwise from lst1
and lst2
DO NOT use
zip
function
[33]:
def szip(lst1, lst2):
raise Exception('TODO IMPLEMENT ME !')
result = szip([3,5,1,6], ['a','d','e','w'])
print(result) # [(3,'a'), (5,'d'), (1,'e'), (6,'w')]
assert szip([], []) == []
assert szip(['a'], [0]) == [('a',0)]
assert szip(['z','a'], [2,4]) == [('z',2), ('a',4)]
assert szip([3,5,1,6], ['a','d','e','w']) == [(3,'a'), (5,'d'), (1,'e'), (6,'w')]
Exercise - sunnest
Given a lst
of lists, RETURN a NEW list without sublists (also called shallow unnest)
assume sublists cannot have further sublists inside
[34]:
def sunnest(lst):
raise Exception('TODO IMPLEMENT ME !')
result = sunnest([[3,2,5], [2,4], [0,9,5,1]])
print(result) # [3,2,5,2,4,0,9,5,1]
assert sunnest([]) == []
assert sunnest([[]]) == []
assert sunnest([[],[]]) == []
assert sunnest([[],[4]]) == [4]
assert sunnest([[3],[]]) == [3]
assert sunnest([[3,2]]) == [3,2]
assert sunnest([[3,2]]) == [3,2]
assert sunnest([[3,2,5], [2,4], [0,9,5,1]]) == [3,2,5,2,4,0,9,5,1]
Exercise - sfib
Given a number n
, RETURN a NEW list with all the numbers of Fibonacci sequence:
\(n\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
---|---|---|---|---|---|---|---|---|---|---|---|
\(x_n\) |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
… |
Base cases:
\(x_0\) = 0
\(x_1\) = 1
The next number is found by adding up the two numbers before it:
\(x_2\) is 0+1
\(x_3\) is 1+1
\(x_4\) is 2+1
\(x_5\) is 3+2
and so on…
[35]:
def sfib(n):
raise Exception('TODO IMPLEMENT ME !')
result = sfib(7)
print(result) # [0,1,1,2,3,5,8,13]
assert sfib(0) == [0]
assert sfib(1) == [0,1]
assert sfib(2) == [0,1,1]
assert sfib(3) == [0,1,1,2]
assert sfib(4) == [0,1,1,2,3]
assert sfib(5) == [0,1,1,2,3,5]
assert sfib(6) == [0,1,1,2,3,5,8]
assert sfib(7) == [0,1,1,2,3,5,8,13]
[0, 1, 1, 2, 3, 5, 8, 13]
Exercise - sall
Given a lst
of booleans, RETURN True
if all elements are True
, otherwise RETURN False
DO NOT use
all
functionassume
sall
of empty list isTrue
HINT: consider exploiting Boolean evaluation order to shorten your code
[36]:
def sall(lst):
raise Exception('TODO IMPLEMENT ME !')
assert sall([]) == True
assert sall([True]) == True
assert sall([False]) == False
assert sall([False, False]) == False
assert sall([False, True]) == False
assert sall([True, False]) == False
assert sall([True, True]) == True
assert sall([False, False, False]) == False
assert sall([False, False, True]) == False
assert sall([False, True, False]) == False
assert sall([False, True, True]) == False
assert sall([True, False, False]) == False
assert sall([True, False, True]) == False
assert sall([True, True, False]) == False
assert sall([True, True, True]) == True
Exercise - srev
Given a list, RETURN a NEW list reversed.
DO NOT use
reversed
functionDO NOT use slice stepping
[37]:
def srev(lst):
raise Exception('TODO IMPLEMENT ME !')
result = srev([4,9,7,5,6])
print(result)
assert srev([]) == []
assert srev([3]) == [3]
assert srev([5,3]) == [3,5]
assert srev([6,6,2]) == [2,6,6]
assert srev([4,9,7,5,6]) == [6,5,7,9,4]
Exercise - spalindrome
A string is palindrome if it reads the same backward as forward.
Given a string s
, return True
if the string is palindrome, otherwise return False
.
we assume the empty string is palindrome
here we use strings but same rules for lists apply
DO NOT use string methods (so no
.index()
,.find()
, …)
[38]:
def spalindrome(s):
raise Exception('TODO IMPLEMENT ME !')
assert spalindrome('') == True
assert spalindrome('a') == True
assert spalindrome('ab') == False
assert spalindrome('cc') == True
assert spalindrome('ddv') == False
assert spalindrome('vddv') == True
assert spalindrome('axyb') == False
assert spalindrome('kayak') == True
assert spalindrome('kayag') == False
assert spalindrome('rotator') == True
assert spalindrome('rotating') == False
assert spalindrome('noon') == True
assert spalindrome('soon') == False
assert spalindrome('abcdba') == False
Exercise - snest
Given a lst
, RETURN a NEW list of deeply right nested lists as in the example
[39]:
def snest(lst):
raise Exception('TODO IMPLEMENT ME !')
result = snest(['a','b','c','d','e','g','h'])
print(result) # ['a',['b',['c',['d',['e',['g',['h']]]]]]]
assert snest([]) == []
assert snest(['a']) == ['a']
assert snest(['a','b']) == ['a',['b']]
assert snest(['a','b','c']) == ['a',['b',['c']]]
assert snest(['x','x','y']) == ['x',['x',['y']]]
assert snest(['a','b','c','d','e','g','h']) == ['a',['b',['c',['d',['e',['g',['h']]]]]]]
Exercise - spalace
Given a lst
of characters, RETURN a NEW list of deeply nested lists as in the example.
Pay attention to base cases, there are several
[40]:
def spalace(lst):
raise Exception('TODO IMPLEMENT ME !')
result = spalace(['a','b','c','d','e','f','g','h','i'])
print(result) # ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']
assert spalace([]) == []
assert spalace(['a']) == ['a']
assert spalace(['a','b']) == ['a','b']
assert spalace(['b','a']) == ['b','a']
assert spalace(['c','b','a']) == ['c',['b'],'a']
assert spalace(['z','w','z']) == ['z',['w'],'z']
assert spalace(['p','x','y','z','q']) == ['p',['x',['y'],'z'],'q']
assert spalace(['a','b','c','d','e','f','g','h','i']) == ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']
Exercise - srep
Given a list la
, and a list lb
of integer numbers \(\geq 0\), RETURN a NEW list where all elements of la
are repeated the amount of times indicated in the corresponding cell of lb
assume
la
andlb
have the same sizeDO NOT use
*
replication operator
[41]:
def srep(la, lb):
raise Exception('TODO IMPLEMENT ME !')
result = srep(['a','b','c','d'], [2,5,0,3])
print(result) # ['a','a','b','b','b','b','b','d','d','d']
assert srep([], []) == []
assert srep(['a'], [1]) == ['a']
assert srep(['a'], [0]) == []
assert srep(['b'], [2]) == ['b','b']
assert srep(['a','b'], [1,1]) == ['a','b']
assert srep(['a','b'], [1,2]) == ['a','b','b']
assert srep(['a','b'], [2,1]) == ['a','a','b']
assert srep(['a','b'], [2,0]) == ['a','a']
assert srep(['a','b'], [0,2]) == ['b','b']
assert srep(['a','b','c'], [1,1,1]) == ['a','b','c']
assert srep(['a','b','c'], [0,1,1]) == ['b','c']
assert srep(['a','b','c'], [0,1,0]) == ['b']
assert srep(['a','b','c'], [3,1,2]) == ['a','a','a','b','c','c']
assert srep(['a','b','c','d'], [2,5,0,3]) == ['a','a','b','b','b','b','b','d','d','d']
Exercise - ssortin
Given two already sorted lists la
and lb
of arbitrary sizes, return True
if all numbers of la
are present in lb
assume empty list is always contained in any list
DO NOT use search methods (
find()
,index()
, …)HINT 1: compare list heads one at a time, try thinking when you can return early
HINT 2: you will need to progress lists at different times
[42]:
def ssortin(la, lb):
raise Exception('TODO IMPLEMENT ME !')
assert ssortin([], []) == True
assert ssortin([], [4,5,8,1]) == True
assert ssortin([5], [5]) == True
assert ssortin([5], [6]) == False
assert ssortin([3], [3,8]) == True
assert ssortin([8], [3,8]) == True
assert ssortin([2], [3,8]) == False
assert ssortin([7,9], [7,9]) == True
assert ssortin([7,9], [3,7,9]) == True
assert ssortin([7,9], [7,8,9]) == True
assert ssortin([7,9], [7,9,10]) == True
assert ssortin([5,8], [2,8]) == False
assert ssortin([5,8], [5,6]) == False
assert ssortin([5,8], [2,4,8]) == False
assert ssortin([5,8], [4,5,7]) == False
assert ssortin([3,5,6], [3,5,6]) == True
assert ssortin([3,5,6], [3,4,5,6]) == True
assert ssortin([3,5,6], [3,5,6,7]) == True
assert ssortin([4,6,11], [1,3,4,5,6,7,8,10,11,12]) == True
Continue
Go on with accumulators worksheet