Recursion 2 - Accumulators and indexes

So far in the SimpleFP model we have been creating a lot of new lists by concatenating with + operator and taking slices: this wasted a lot of memory and computation time.

Let’s try to improve performance by creating a new model we named ModAcc with these requirements:

ALLOWED:

  • add helper functions to easily pass extra variables

  • add special accumulator parameters to the helper function: feel free to MODIFY them (and only them!) by using .append, .extend, etc

  • add indexes parameters to the helper function to keep track where to look in the original list

  • getting length with len(lst)

  • in operator on dictionaries or sets

DO NOT use slices

DO NOT MODIFY input parameters!

DO NOT use in operator on 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!

DO NOT INITIALIZE AN ACCUMULATOR IN THE PARAMETER DECLARATION

  • NEVER write stuff like:

def my_helper(lst, acc=[]):
def my_helper(lst, acc={}):

If you initialize to a mutable data structure such as lists or dictionaries, Python will create exactly one memory region for all function invocations, which is quite counterintuitive and bug prone!

Example - adouble

Let’s see an example by improving our double function to take a lst of numbers and RETURN a NEW list with the numbers doubled:

[2]:
def adouble_helper(lst, i, acc):   # we create a helper function
                                   # with index where to start looking
                                   # and accumulator variable
                                   # note acc is *not* initialized in the parameters
    if i == len(lst):   # base case compares index against end of list
        return acc      #    notice it returns the accumulator
    else:
        acc.append(lst[i]*2)    #  we first MODIFY the accumulator
        return adouble_helper(lst, i+1, acc)  # then do recursion by passing the modified accumulator
                                                # notice passed list is always the same,
                                                # what changes is the starting index

def adouble(lst):
    return adouble_helper(lst, 0, [])

result = adouble([7,9,5])
result
jupman.pytut()
[2]:

Exercise - debug adouble

Add a level parameter and some debugging indented print to the function

Show solution
[4]:

result = adouble([4,9,1,5,7,3])
result
 i= 0  acc= []
  i= 1  acc= [8]
   i= 2  acc= [8, 18]
    i= 3  acc= [8, 18, 2]
     i= 4  acc= [8, 18, 2, 10]
      i= 5  acc= [8, 18, 2, 10, 14]
       i= 6  acc= [8, 18, 2, 10, 14, 6]
      res= [8, 18, 2, 10, 14, 6]
     res= [8, 18, 2, 10, 14, 6]
    res= [8, 18, 2, 10, 14, 6]
   res= [8, 18, 2, 10, 14, 6]
  res= [8, 18, 2, 10, 14, 6]
 res= [8, 18, 2, 10, 14, 6]
[4]:
[8, 18, 2, 10, 14, 6]

Exercise - afilter_even

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

Show solution
[5]:




def afilter_even(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = afilter_even([3,7,10,5,4,8,6,11])
print(result)  # [10,4,8,6]

assert afilter_even([3]) == []
assert afilter_even([4]) == [4]
assert afilter_even([3,6]) == [6]
assert afilter_even([8,3]) == [8]
assert afilter_even([8,3,2]) == [8,2]
assert afilter_even([7,7,8,3,2]) == [8,2]
assert afilter_even([3,7,10,5,4,8,6,11]) == [10,4,8,6]

Exercise - amerry

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




def amerry(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = amerry(['a','b','c','c','a','d','b','a'])
print(result)  # [['a','b'],['c','c'],['a','d'],['b','a']]

assert amerry([]) == []
assert amerry(['d','b']) == [['d','b']]
assert amerry(['a','a','b','b']) == [['a','a'],['b','b']]
assert amerry(['a','b','c','d']) == [['a','b'],['c','d']]
assert amerry(['a','b','c','c','a','d','b','a']) == [['a','b'],['c','c'],['a','d'],['b','a']]

Exercise - afib

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


def afib(n):
    raise Exception('TODO IMPLEMENT ME !')

result = afib(7)
print(result) # [0,1,1,2,3,5,8,13]

assert afib(0) == [0]
assert afib(1) == [0,1]
assert afib(2) == [0,1,1]
assert afib(3) == [0,1,1,2]
assert afib(4) == [0,1,1,2,3]
assert afib(5) == [0,1,1,2,3,5]
assert afib(6) == [0,1,1,2,3,5,8]
assert afib(7) == [0,1,1,2,3,5,8,13]
[0, 1, 1, 2, 3, 5, 8, 13]

Exercise - asearch

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, ….

  • you might consider shortening your code by using Boolean evaluation order

Show solution
[8]:


def asearch(el, lst):
    raise Exception('TODO IMPLEMENT ME !')

print(asearch(7, [6,4,7,8]))   # True
print(asearch(5, [6,4,7,8]))   # False

assert asearch(7, [6,4,7,8]) == True
assert asearch(7, [8]) == False
assert asearch(8, [8]) == True
assert asearch(5, [8,5]) == True
assert asearch(2, [8,5]) == False
assert asearch(7, [7,8,5]) == True
assert asearch(2, [8,2,5]) == True
assert asearch(9, [7,8,9]) == True
assert asearch(2, [8,9,5]) == False

Exercise - azip

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



def azip(lst1, lst2):
    raise Exception('TODO IMPLEMENT ME !')

result = azip([3,5,1,6], ['a','d','e','w'])
print(result)  # [(3,'a'), (5,'d'), (1,'e'), (6,'w')]

assert azip([], []) == []
assert azip(['a'], [0]) == [('a',0)]
assert azip(['z','a'], [2,4]) == [('z',2), ('a',4)]
assert azip([3,5,1,6], ['a','d','e','w']) == [(3,'a'), (5,'d'), (1,'e'), (6,'w')]

Exercise - aunnest

Given a lst of lists, RETURN a NEW list without sublists (also called shallow unnest)

  • assume sublists cannot have further sublists inside

Show solution
[11]:



def aunnest(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = aunnest([[3,2,5], [2,4], [0,9,5,1]])
print(result)  # [3,2,5,2,4,0,9,5,1]

assert aunnest([]) == []
assert aunnest([[]]) == []
assert aunnest([[],[]]) == []
assert aunnest([[],[4]]) == [4]
assert aunnest([[3],[]]) == [3]
assert aunnest([[3,2]]) == [3,2]
assert aunnest([[3,2]]) == [3,2]
assert aunnest([[3,2,5], [2,4], [0,9,5,1]]) == [3,2,5,2,4,0,9,5,1]

Exercise - arev

Given a list, RETURN a NEW list reversed.

  • DO NOT use reversed function

  • DO NOT use slice stepping

Show solution
[12]:

def arev(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = arev([4,9,7,5,6])
print(result)

assert arev([]) == []
assert arev([3]) == [3]
assert arev([5,3]) == [3,5]
assert arev([6,6,2]) == [2,6,6]
assert arev([4,9,7,5,6]) == [6,5,7,9,4]

Exercise - apalindrome

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

def apalindrome(s):
    raise Exception('TODO IMPLEMENT ME !')

assert apalindrome('') == True
assert apalindrome('a') == True
assert apalindrome('ab') == False
assert apalindrome('cc') == True
assert apalindrome('ddv') == False
assert apalindrome('vddv') == True
assert apalindrome('axyb') == False
assert apalindrome('kayak') == True
assert apalindrome('kayag') == False
assert apalindrome('rotator') == True
assert apalindrome('rotating') == False
assert apalindrome('noon') == True
assert apalindrome('soon') == False
assert apalindrome('abcdba') == False

Exercise - anest

Given a lst, RETURN a NEW list of deeply right nested lists as in the example

  • HINT: you need to create a new list anyway at each helper call

Show solution
[14]:

def anest(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = anest(['a','b','c','d','e','g','h'])
print(result)  # ['a',['b',['c',['d',['e',['g',['h']]]]]]]

assert anest([]) == []
assert anest(['a']) == ['a']
assert anest(['a','b']) == ['a',['b']]
assert anest(['a','b','c']) == ['a',['b',['c']]]
assert anest(['x','x','y']) == ['x',['x',['y']]]
assert anest(['a','b','c','d','e','g','h']) == ['a',['b',['c',['d',['e',['g',['h']]]]]]]

Exercise - apalace

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

  • HINT: you need to create a new list anyway at each helper call

Show solution
[15]:




def apalace(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = apalace(['a','b','c','d','e','f','g','h','i'])
print(result)   # ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

assert apalace([])  == []
assert apalace(['a'])  == ['a']
assert apalace(['a','b'])  == ['a','b']
assert apalace(['b','a'])  == ['b','a']
assert apalace(['c','b','a'])  == ['c',['b'],'a']
assert apalace(['z','w','z'])  == ['z',['w'],'z']
assert apalace(['p','x','y','z','q'])  == ['p',['x',['y'],'z'],'q']
assert apalace(['a','b','c','d','e','f','g','h','i'])  == ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

Exercise - arep

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

  • HINT: you will need an additional parameter k in the helper to keep track of the amount of repetitions left

Show solution
[16]:



def arep(la, lb):
    raise Exception('TODO IMPLEMENT ME !')

result = arep(['a','b','c','d'], [2,5,0,3])
print(result) # ['a','a','b','b','b','b','b','d','d','d']

assert arep([], []) == []
assert arep(['a'], [1]) == ['a']
assert arep(['a'], [0]) == []
assert arep(['b'], [2]) == ['b','b']
assert arep(['a','b'], [1,1]) == ['a','b']
assert arep(['a','b'], [1,2]) == ['a','b','b']
assert arep(['a','b'], [2,1]) == ['a','a','b']
assert arep(['a','b'], [2,0]) == ['a','a']
assert arep(['a','b'], [0,2]) == ['b','b']
assert arep(['a','b','c'], [1,1,1]) == ['a','b','c']
assert arep(['a','b','c'], [0,1,1]) == ['b','c']
assert arep(['a','b','c'], [0,1,0]) == ['b']
assert arep(['a','b','c'], [3,1,2]) == ['a','a','a','b','c','c']
assert arep(['a','b','c','d'], [2,5,0,3]) == ['a','a','b','b','b','b','b','d','d','d']

Exercise - asortin

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 a couple of indexes in the helper (you don’t need an accumulator)

Show solution
[17]:

def asortin(la, lb):
    raise Exception('TODO IMPLEMENT ME !')

assert asortin([], []) == True
assert asortin([], [4,5,8,1]) == True
assert asortin([5], [5]) == True
assert asortin([5], [6]) == False
assert asortin([3], [3,8]) == True
assert asortin([8], [3,8]) == True
assert asortin([2], [3,8]) == False
assert asortin([7,9], [7,9]) == True
assert asortin([7,9], [3,7,9]) == True
assert asortin([7,9], [7,8,9]) == True
assert asortin([7,9], [7,9,10]) == True
assert asortin([5,8], [2,8]) == False
assert asortin([5,8], [5,6]) == False
assert asortin([5,8], [2,4,8]) == False
assert asortin([5,8], [4,5,7]) == False
assert asortin([3,5,6], [3,5,6]) == True
assert asortin([3,5,6], [3,4,5,6]) == True
assert asortin([3,5,6], [3,5,6,7]) == True
assert asortin([4,6,11], [1,3,4,5,6,7,8,10,11,12]) == True

Exercise - ahist

Given a lst, RETURN a NEW dictionary with the counts of elements of lst

  • DO NOT use search methods (.index, .count, .remove…)

Show solution
[18]:



def ahist(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = ahist(['a','b','a','c','b','b','c','a','b','c','d'])
print(result)  # {'a':3,
               #  'b':4,
               #  'c':3,
               #  'd':1}

assert ahist([]) == {}
assert ahist(['a']) == {'a':1}
assert ahist(['a','a']) == {'a':2}
assert ahist(['a','b']) == {'a':1,
                            'b':1}
assert ahist(['b','c']) == {'c':1,
                            'b':1}
assert ahist(['a','c','a']) == {'a':2,
                                'c':1}
assert ahist(['c','c','a']) == {'a':1,
                                'c':2}
assert ahist(['a','b','a','c','b','b','c','a','b','c','d']) == {'a':3,
                                                                'b':4,
                                                                'c':3,
                                                                'd':1}

Exercise - agap

In a list \(L\) containing \(n≥2\) integers, a gap is an index \(i\), \(0< i < n\), such that \(L[i−1]< L[i]\)

If \(n≥2\) and \(L[0]< L[n−1]\), \(L\) contains at least one gap.

Design an algorithm that, given a list \(L\) containing \(n≥2\) integers such that \(L[0]< L[n−1]\), finds a gap in the list.

We wrote here the gap function as pseudocode, try coding it in Python:

recursive gap jiuiu9

Use the following skeleton and add some test. To understand what’s going on, try copy-pasting in Python tutor

CAREFUL ABOUT agap ASSUMPTIONS!

The specification of agap assumes the input is always a list of at least two elements, and that the first element is less or equal than the last one. If these conditions are not met, function behaviour could be completely erroneus!

When preconditions are not met, execution could stop because of an error like index out of bounds, or, even worse, we might get back some wrong index as a gap! To prevent misuse of the function, a good idea can be putting a check at the beginning of the agap function. Such check should immediately stop the execution and raise an error if the parameters don’t satisfy the preconditions. One way to do this could be adding some assertion that will make python interrupt execution and throw an error as soon it detects list L is too small or with wrong values * This kind of behaviour is also called fail fast, which is better than returning wrong values! * You can put any condition you want after assert, but ideally they should be fast to execute. * asserts might be better here than raise Exception constructs because asserts can be disabled with a flag passed to the interpreter. So, when you debug you can take advantage of them, and when the code is production quality and supposed to be bug free you can disable all assertions at once to gain in execution speed.

GOOD PRACTICE: Notice we wrote what the helper function is expected to receive as a comment. Writing down specs often helps understanding what the function is supposed to do, and helps users of your code as well!

VII COMMANDMENT: You shall also write on paper!

To get an idea of how agap is working, draw histograms on paper like the following, with different heights at index m:

gap rec histogram 098983ju

Notice how at each recursive call, we end up with a histogram that is similar to the inital one, that is, it respects the same preconditions (a list of size \(\geq 2\) where first element is smaller or equal than the last one)

Show solution
[19]:

def agap_helper(L, i, j):
    raise Exception('TODO IMPLEMENT ME !')

def agap(L):
    raise Exception('TODO IMPLEMENT ME !')




# try also to write asserts

Continue

Go on with divide and conquer strategy