FAQ: Recursion: Python - Stack Over-Whoa!

This community-built FAQ covers the “Stack Over-Whoa!” exercise from the lesson “Recursion: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Learn Recursion: Python

FAQs on the exercise Stack Over-Whoa!

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

My bad, it was wrong the codes in the deleted post. See the one below.

The following codes in 5. Stack overflow Whoa! explanations part are incorrect and generated IndexErrors.

def power_set(set):
power_set_size = 2**len(set)
result =

for bit in range(0, power_set_size):
sub_set =
for binary_digit in range(0, len(set)):
if((bit & (1 << binary_digit)) > 0):
sub_set.append(set[bit])
result.append(sub_set)
return result

Traceback (most recent call last):
File “recursion.py”, line 16, in
print(power_set(test))
File “recursion.py”, line 9, in power_set
sub_set.append(set[bit])
IndexError: list index out of range

The line sub_set.append(set[bit]) is wrong because “bit” has the number of index from 2len(set) which is way more than the actual number of items in “set”. The correct codes I believe should be sub_set.append(set[binary_digit]) for that line and the entire set of codes can be updated as
def power_set(set):
power_set_size = 2
len(set)
result =

for bit in range(0, power_set_size):
sub_set =
for binary_digit in range(0, len(set)):
if ((bit & (1 << binary_digit)) > 0):
if set[binary_digit] not in sub_set:
sub_set.append(set[binary_digit])
result.append(sub_set)
return result
Output - [, [‘a’], [‘b’], [‘a’, ‘b’], [‘c’], [‘a’, ‘c’], [‘b’, ‘c’], [‘a’, ‘b’, ‘c’]]

1 Like

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.

1 Like

Hi. I am really having trouble understanding how [‘STANFORD’] is retrieved from pswf (power_set_without_first) given that the function recurses with the original list each time, just without the first item (my_list[1:]).

Here is my logic for pswf when the list is [‘UCLA’, ‘STANFORD’, ‘NYU’]: Function is invoked with this list and then reaches “power_set_without_first = power_set(my_list[1:])” . So this function must now call [‘STANFORD’, ‘NYU’] and thus it it placed on the call_stack.

The power_set function is now invoked with [‘STANFORD’, ‘NYU’] and reaches the same line again “power_set_without_first = power_set(my_list[1:])” which calls [‘NYU’] thus this is placed on the call_stack. The recurses and retrieves the base case of [empty].

As you can see, when the list is [‘UCLA’, ‘STANFORD’, ‘NYU’] I am only able to see how psfw retrieves:
[[‘STANFORD’, ‘NYU’], [‘NYU’], [empty]] and not [[‘STANFORD’, ‘NYU’], [‘STANFORD’], [‘NYU’], [empty]] like the the solution in the module states.

I know I am missing something here, but any thoughts to help me understand this? I am thinking that [‘STANFORD’, ‘NYU’] must call both [‘STANFORD’] and [‘NYU’] but am unsure of how/why given that it is still a recursive function.

1 Like

Actually I added print statements and changed the list to numbers to make it more straightforward and I see whats happening here.

def power_set(my_list):

if len(my_list) == 0:
return []

power_set_without_first = power_set(my_list[1:])
print (“pswf:”)
print (power_set_without_first)

with_first = [ [my_list[0]] + rest for rest in power_set_without_first ]
print (“wf:”)
print (with_first)

print (“wf + pswf:”)
print (with_first + power_set_without_first)
return with_first + power_set_without_first

numbers = [“1”, “2”, “3”]

power_set_of_numbers = power_set(numbers)

print (" ")
print (“Result:”)

for set in power_set_of_numbers:
print(set)

RESULT:

pswf:
[]
wf:
[[‘3’]]
wf + pswf:
[[‘3’], ]
pswf:
[[‘3’], ]
wf:
[[‘2’, ‘3’], [‘2’]]
wf + pswf:
[[‘2’, ‘3’], [‘2’], [‘3’], ]
pswf:
[[‘2’, ‘3’], [‘2’], [‘3’], ]
wf:
[[‘1’, ‘2’, ‘3’], [‘1’, ‘2’], [‘1’, ‘3’], [‘1’]]
wf + pswf:
[[‘1’, ‘2’, ‘3’], [‘1’, ‘2’], [‘1’, ‘3’], [‘1’], [‘2’, ‘3’], [‘2’], [‘3’], []]

Which is the expected result.

So the stack looks like this from top to bottom [ ‘’, ‘[3]’, ‘[2], [3]’, ‘[1], [2], [3]’] So for some reason it is popping the top item of the “power_set_without_first = power_set(my_list[1:])” stack which is an empty list, , and using that as the base input for “with_first”.

Then “with_first” uses the previous item in the stack, [3], as [my_list[0]] giving us [[‘3’], ] for “pswf + wf”.

The function then uses this as the new pswf. “with_first” then recurses one place further down the call stack, and coincidentally the list, to [2]. So “[2] + rest for rest in pswf” = wf = [2,3] and [2]. So pswf + wf = [[‘2’, ‘3’], [‘2’], [‘3’], ] and this becomes the new pswf. So we move down the list once again to [1] and wf = [[‘1’, ‘2’, ‘3’], [‘1’, ‘2’], [‘1’, ‘3’], [‘1’]]. And so on and so on

1 Like

Hi All, I still struggle to understand how the function uses the new pswf value and recurses. The start pswf is an empty list and wf+pswf is [[‘3’],[0]] but how the wf+pswf becomes pswf again and adds 2 etc?

Is this the right forum for discussing the structure of the lesson itself?

'Cause I feel a little bit cheated! I understand the maths behind the powerset and how the binary system allows 2^N possible numbers for N binary digits, so why explain so much correlation, and pull me away from the whole recursion if you’re going to drop a “you’re not smart enough line”? :frowning:

Learn recursion python - stackoverwhoa

Here is the complete solution. You’re not expected to understand every line, just take in the level of complexity.

def power_set(set):
  power_set_size = 2**len(set)
  result = []

  for bit in range(0, power_set_size):
    sub_set = []
    for binary_digit in range(0, len(set)):
      if((bit & (1 << binary_digit)) > 0):
        sub_set.append(set[binary_digit])
    result.append(sub_set)
  return result

Okay first of all, this code doesn’t look THAT complex…
Secondly, I really don’t like examples that I am not supposed to understand… And surely I don’t understand this one, because the preceding explanation is very poor in terms of python code, such as:

set = ['a', 'b', 'c']
binary_number = "101"
# produces the subset ['a', 'c']
# 'b' is left out because its binary digit is 0

(It doesn’t actually do anything except creating two variables…)

Which finally brings me to case-study conclusion quote (which also could double as a subtitle to the whole intro of this lesson):

(I would love to rewrite this commend describing how much I liked both methods explained PROPERLY in order to make the comparison.)