Skip to content

Question 38

What is the output of the following code?

1
2
3
4
5
6
7
8
9
def f(seq):
    if not seq:
        return seq
    if type(seq) != list:
        return seq
    return [f(seq[0])]*2 + f(seq[1:])

lst = [1,[2]]
print(f(lst))
Hint

f() seems to be a recursive function that acts on the contents and/or value of seq.

Solution

Inside f(),

  • if seq is an empty list, return seq (where seq = [])
  • else if seq is not a list, return a new list containing seq inside it
  • else, return 2 times of the result of the recursive call to f() containing the first element as the parameter, concatenated with the result of the recursive call to f() contianing a list of the rest of the elements
f(lst) = f([1, [2]])
= [f(1)]*2 + f([[2]])
= [1]*2 + f([[2]])
= [1, 1] + f([[2]])
= [1, 1] + [f([2])]*2 + f([])
= [1, 1] + [[f(2)]*2 + f([])]*2 + f([])
= [1, 1] + [[2]*2 + []]*2 + f([])
= [1, 1] + [[2, 2] + []]*2 + f([])
= [1, 1] + [[2, 2]]*2 + f([])
= [1, 1] + [[2, 2], [2, 2]] + f([])
= [1, 1] + [[2, 2], [2, 2]] + []
= [1, 1, [2, 2], [2, 2]]
Answer 
[1, 1, [2, 2], [2, 2]]