The key to this recursive problem (and most) is understanding mathematical induction -
def my_remove(the_char, the_list):
if the_list == []: #1
return the_list
elif isinstance(the_list[0],list): #2
return my_remove(the_char, the_list[0]) \
+ my_remove(the_char, the_list[1:])
elif the_list[0] == the_char: #3
return my_remove(the_char, the_list[1:])
else: #4
return [ the_list[0] ] + my_remove(the_char, the_list[1:])
input = ['a','z',['z','b',['c','z','z']],[['d']],'z']
print(my_remove('z', input))
# ['a','b','c','d']
In the numbered comments -
terminating condition and base case: when the input is empty, return an empty output
otherwise, by induction, the list is not empty. If the first element of the list is another list, combine the result of calling my_remove
on the first element and my_remove
on the tail of the list, list[1:]
otherwise, by induction, the list is not empty and the first element of the list is not a list. If the first element matches the char, simply call my_remove
on the tail of the list.
otherwise, by induction, the list is not empty and the first element is of the list is not a list, and the first element of the list does not match the char. Include the first element of the list in the output and combine it with my_remove
called on the tail of the list
Your question explicitly says that helper functions cannot be used. This is most likely an indication of a bad programming teacher. Helper functions make it possible to remove complexity from your program, thereby gaining a complexity-free mind.
Given some generic functions for working on lists -
def isEmpty(l):
return len(l) == 0
def isList(l):
return isinstance(l, list)
def head(l):
return l[0]
def tail(l):
return l[1:]
We can write my_remove
with a richer semantics that immediately communicates its intentions to the reader -
def my_remove(x, lst):
if isEmpty(lst):
return lst
elif isList(head(lst)):
return my_remove(x, head(lst)) \
+ my_remove(x, tail(lst))
elif head(lst) == x:
return my_remove(x, tail(lst))
else:
return [ head(lst) ] + my_remove(x, tail(lst))
The output is the same, of course -
print(my_remove('z', input))
# ['a','b','c','d']
These helpers could be further improved to protect the programmer for their misuse. Ie, raising a RuntimeWarning
is a good way to let you know you made a mistake with your inductive reasoning -
def isEmpty(l):
return isList(l) and len(l) == 0
def isList(l):
return isinstance(l, list)
def head(l):
if isEmpty(l):
raise RuntimeWarning('head called on empty list')
else:
return l[0]
def tail(l):
if isEmpty(l):
raise RuntimeWarning('tail called on empty list')
else:
return l[1:]