From the base case through the recursion

For those who are struggling on what is happening step by step from the base case through the recursion, here it is (I wish somebody did this before me, it took me some minutes to crack it, so i hope this will help):

few abbreviations to make reading easier:
“[empty] is the base case”
“power_set_without_first = pswf”
“without_first = wf”

I.- when the list is just [empty]:
pswf = [empty]
wf = [empty]
pswf + wf = [empty]

II.- when the list is [‘NYU’]:
pswf = [empty] (we now this from the previous recursion)
wf = [[‘NYU’] + [empty]] = [‘NYU’]
pswf + wf = [‘NYU’] (here is actually [‘NYU’, ‘empty’])

III.- when the list is [‘STANFORD’, ‘NYU’]:
pswf = [‘NYU’, [empty]]
(i think the trick here is understanding that is a list with NYU and ‘empty’, so later in “with first” there is will be a case when you sum the [my_list[0]] with [empty]. You can prove this, by replacing the base case with [1] instead of [empty] in the code and see what happens.
wf = [[[‘STANFORD’] + [empty]], [[‘STANFORD’] + [‘NYU’]]]
wf = [[‘STANFORD’], [‘STANFORD’, ‘NYU’]]
pswf + wf = [[empty], [‘NYU’], [‘STANFORD’], [‘STANFORD’, ‘NYU’]]

IV.- when the list is [‘UCLA’, ‘STANFORD’, ‘NYU’]:
pswf = [[empty], [‘NYU’], [‘STANFORD’], [‘STANFORD’, ‘NYU’]]
wf = [[[‘UCLA’] + [empty], [‘UCLA’] + [‘NYU’], [‘UCLA’] + [‘STANFORD’], ['UCLA] + [‘STANFORD’, ‘NYU’]]]
wf = [[‘UCLA’], [‘UCLA’, ‘NYU’], [‘UCLA’, ‘STANFORD’], [‘UCLA’, ‘STANFORD’, ‘NYU’]]
pswf + wf = [[empty], [‘NYU’], [‘STANFORD’], [‘STANFORD’, ‘NYU’], [‘UCLA’], [‘UCLA’, ‘NYU’], [‘UCLA’, ‘STANFORD’], [‘UCLA’, ‘STANFORD’, ‘NYU’]]

and this go on to the final case with ‘MIT’ included.

Please if anybody finds an error on this, feel free to reply.

8 Likes