Skip to content

Question 37

What is the output of the following code?

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

lst = [1,2,[3,4],[5,[6,7]]]
print(f(lst))
Hint

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

Solution

f() is a instance of deep sorting of each numerical element inside seq. 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 a recursive call to f() with passing in seq[1:] as the parameter, and concatenating it with yet another recursive call to f() with passing in seq[0] as the parameter
f(lst) = f([1, 2, [3, 4], [5, [6, 7]]])
= f([2, [3, 4], [5, [6, 7]]]) + f(1)
= f([[3, 4], [5, [6, 7]]]) + f(2) + f(1)
= f([[5, [6, 7]]]) + f([3, 4]) + f(2) + f(1)
= f([]) + f([5, [6, 7]]) + f([3, 4]) + f(2) + f(1)
= f([]) + f([[6, 7]]) + f(5) + f([3, 4]) + f(2) + f(1)
= f([]) + f([]) + f([6, 7]) + f(5) + f([3, 4]) + f(2) + f(1)
= f([]) + f([]) + f([7]) + f(6) + f(5) + f([3, 4]) + f(2) + f(1)
= f([]) + f([]) + f([]) + f(7) + f(6) + f(5) + f([3, 4]) + f(2) + f(1)
= f([]) + f([]) + f([]) + f(7) + f(6) + f(5) + f([4]) + f(3) + f(2) + f(1)
= f([]) + f([]) + f([]) + f(7) + f(6) + f(5) + f([]) + f(4) + f(3) + f(2) + f(1)
= f([]) + f([]) + f([]) + f(7) + f(6) + f(5) + f([]) + f(4) + f(3) + f(2) + f(1)
= [] + [] + [] + [7] + [6] + [5] + [] + [4] + [3] + [2] + [1]
= [7, 6, 5, 4, 3, 2, 1]
Answer 
[7, 6, 5, 4, 3, 2, 1]