In all these problems you will need to use recursion.
And perhaps loops too.
** But they are difficult to solve without any recursion at all. **
---------------------------------
Depth of a list.
the depth of a list is the maximum number of nestings
of lists-inside-lists that it contains.
For example, the depth
of [1,2,3] is 1, the depth of [1,[2,3],4] is 2,
the depth of [[[[[1]]]]] is 5, the depth of
[[4,5],1,[2,[3,4],[5,6]]] is 3. The depth of []
is defined to be 0.
To see intuitively why we call it depth, write
the list as a tree and then the depth of the list
is the depth of the tree.
Write a python function that takes a list lst
and returns its depth.
Hint:
if lst is the empty list, then its depth is 0.
if lst is not the empty list, it has a first
element x and a rest of the list lst1.
Suppose you know the depth of lst1 - recursively
Now, if x is not a list, think what the depth
of lst is.
And if x is a list, what is the depth of lst?
---------------------------------
Maximum of a nested list.
A nested list if a list some of whose elements are lists.
Write a function max(L) that returns the maximum integer
found in a nested list. If there is no integer in the nested list,
it should return None.
For example, for L = [[3,[[5,"hat",1]],3,12.5,[True,2,9,1]],[[],[-8],[3,"earth","90",7,[-5]]]]
max(L) should return 9.
In a first version, assume that the list is non-empty, and that it contains
no empty lists, and that it contains only non-negative integers
------------------------------------------
------------------------------------------
Solutions:
Depth of a list. The key observation
is that if
L = [L1, L2, L3, ...., Lk]
then the depth of L is the maximum of the depths
of L1, ...., Lk, plus 1.
def depth(lst):
if isinstance(lst,list) and len(lst) > 0:
m = 0
for x in lst:
m = max(m,depth(x))
return m+1
else: # something not a list, or the empty list
return 0
----------------
Maximum of a nested list:
def max(L):
if is_instance(L,int):
return L
else: # we assume then it is non-empty
m = max(L[0])
for i in range(1:len(L)):
m = max(m,max(L[i]))
return m
To do the full version, there has to be another
case in which L is not a list, or an empty list,
and also the assignment m = max(...,...)
has to be more careful in case one or both of the arguments are None.