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:

• Andrea Passerini slides on programming paradigms

• Andrea Passerini slides on recursion theory

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 execution

  • calling 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:

x = 3
x = x + 1  # don't

Instead, feel free to create new variables at will:

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 [, ]

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:

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:

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

lst = [5,2,8,7,1,3]

lst[0]

5

lst[4]

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

lst = ['a','b','c','d','e','f','g','h','i']
lst[1:]

['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

lst[len(lst)//2:]

['e', 'f', 'g', 'h', 'i']

lst[:len(lst)//2]

['a', 'b', 'c', 'd']

lst[0:5:2]  # don't use stepping

['a', 'c', 'e']

QUESTION: If we used numpy arrays, would we waste memory when slicing?

Show answer

ANSWER: no, numpy slicing (and only numpy slicing) provides a view on the original data without copying, thus taking slices is a fast operation. Since in purely functional model we force ourselves to never modify data, we could consider access to original data as safe.

SimpleFP - 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!

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:

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:

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

def scount(n):
    if n <= 0:
        return []
    else:
        return scount(n - 1) + [n]

scount(3)
jupman.pytut()

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!

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

[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:

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]

[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:

1. check sequence length

2. if base case, immediately return something

3. otherwise, do recursion on the rest of the sequence

4. combine recursion result in some way with first element

5. 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:

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()

Exercise - debug double

Try placing extra debug prints and separating the steps in the code above

Show solution

def sdouble(lst, level=0):
    print(' '*level, 'lst=', lst)
    if len(lst) == 0:
        return []              # base case
    else:
        res = sdouble(lst[1:], level+1)
        print(' '*level, 'res=', res)
        return [lst[0]*2] + res     # returning operation containing
                                    # a recursive call on a smaller input

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]

[8, 18, 2, 10, 14, 6]

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]

[8, 18, 2, 10, 14, 6]

Exercise - sfilter_even

Takes a lst of numbers, and RETURN a NEW list with only the even numbers

Show solution

def sfilter_even(lst):

    if len(lst) == 0:
        return []
    else:
        if lst[0] % 2 == 0:
            return [lst[0]] + sfilter_even(lst[1:])
        else:
            return sfilter_even(lst[1:])


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]

[10, 4, 8, 6]

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.

Show solution

def smerry(lst):

    if len(lst) == 0:
        return []
    else:
        return [[lst[0], lst[1]]] + smerry(lst[2:])


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']]

[['a', 'b'], ['c', 'c'], ['a', 'd'], ['b', 'a']]

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 ;-)

Show solution

def ssum(lst):

    if len(lst) == 0:
        return 0
    else:
        return lst[0] + ssum(lst[1:])


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

15

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

Show solution

import math
def smin(lst):

    if  len(lst) == 1:
        return lst[0]
    else:
        res = smin(lst[1:])
        if lst[0] < res:
            return lst[0]
        else:
            return res


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

-10

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

Show solution

def ssearch(el, lst):

    if len(lst) == 0:
        return False
    else:
        return lst[0] == el or ssearch(el, lst[1:])  # early termination using  boolean evaluation order!


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

True
False

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

Show solution

def sbin_search(el, lst):


    k = len(lst) // 2
    if len(lst) == 0:
        return False
    elif el == lst[k]:
        return True
    elif el < lst[k]:
        return sbin_search(el, lst[:k])
    else: # >
        return sbin_search(el, lst[k+1:])


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

True
False

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

Show solution

def szip(lst1, lst2):

    if len(lst1) == 0:
        return []
    else:
        return [(lst1[0], lst2[0])] +  szip(lst1[1:], lst2[1:])


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')]

[(3, 'a'), (5, 'd'), (1, 'e'), (6, 'w')]

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

Show solution

def sunnest(lst):

    if len(lst) == 0:
        return []
    else:
        return lst[0] + sunnest(lst[1:])


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]

[3, 2, 5, 2, 4, 0, 9, 5, 1]

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…

Show solution

def sfib(n):

    if n == 0:
        return [0]
    elif n == 1:
        return [0,1]
    else:
        prev = sfib(n-1)
        return prev + [prev[n-1] + prev[n-2]]


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]

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 function

• assume sall of empty list is True

• HINT: consider exploiting Boolean evaluation order to shorten your code

Show solution

def sall(lst):

    if len(lst) == 0:
        return True
    else:
        return lst[0] and sall(lst[1:])  # note if lst[0] is False evaluation stops immediately


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

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 function

• DO NOT use slice stepping

Show solution

def srev(lst):

    if len(lst) == 0:
        return []
    else:
        return srev(lst[1:]) + [lst[0]]


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]

[6, 5, 7, 9, 4]

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(), …)

Show solution

def spalindrome(s):

    if len(s) == 0:
        return True
    elif len(s) == 1:
        return True
    else:
        if s[0] == s[-1]:
            return spalindrome(s[1:-1])
        else:
            return False


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

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

Show solution

def snest(lst):

    if len(lst) == 0:
        return []
    elif len(lst) == 1:
        return [lst[0]]
    else:
        return [lst[0], snest(lst[1:])]


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']]]]]]]

['a', ['b', ['c', ['d', ['e', ['g', ['h']]]]]]]

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

Show solution

def spalace(lst):

    if len(lst) == 0:
        return []
    elif len(lst) == 1:
        return [lst[0]]
    elif len(lst) == 2:
        return [lst[0],lst[1]]
    else:
        return [lst[0], spalace(lst[1:-1]),lst[-1]]


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']

['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

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 and lb have the same size

• DO NOT use * replication operator

Show solution

def srep(la, lb):

    if len(la) == 0:
        return []
    elif lb[0] > 0:
        return [la[0]] + srep(la, [lb[0]-1] + lb[1:])
    else:  # == 0
        return srep(la[1:], lb[1:])


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']

['a', 'a', 'b', 'b', 'b', 'b', 'b', 'd', 'd', 'd']

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

Show solution

def ssortin(la, lb):

    if len(la) == 0:
        return True
    elif len(lb) == 0:
        return False
    elif la[0] < lb[0]:
        return False
    elif la[0] > lb[0]:
        return ssortin(la, lb[1:])
    else:   # l[0] == lb[0]
        return ssortin(la[1:], lb[1:])


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

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