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!

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!

A post was split to a new topic: Explanations part are incorrect and generated IndexErrors

A post was split to a new topic: From the base case through the recursion

2 posts were split to a new topic: How [‘STANFORD’] is retrieved from pswf

A post was split to a new topic: Discussing the structure of the lesson itself - stackoverwhoa!

A post was split to a new topic: How does binary_number variable produces subset ‘a’ and ‘c’ out of the blue

2 posts were merged into an existing topic: From the base case through the recursion

Hello,
Pls help me understand this : what is " # 1 binary digit, 2 numbers " ?

1 binary digit, 2 numbers

0 in binary

0

1 in binary

1

2 binary digits, 4 numbers

00 => 0

01 => 1

10 => 2

11 => 3

If you’re dropping code to the forums or posting text that uses symbols that markdown interprets then How do I format code in my posts? can help keep it in check.

It is just referring to how many integer numbers can be represented by a single binary digit, the examples show integer 0 and integer 1 represented in binary. Then, with two binary digits you can represent a total of 4 integer numbers and so on.

power_set_without_first = power_set(my_list[1:])  # why does it move forward when len(my_list) == 1???
print('###################')

Not sure if I’ve interpreted you correctly but I’ll give it a shot.

If you’ve reduced my_list down to a single element then you’re passing an empty slice-

x = [3]  # slicing outside the index range of a list with one element-
x[1:] == []  # empty list

In your code that call to power_set will hit the base case conditional about if len(my_list) == 0 and return [] at that point because you passed an empty list as the argument.

To put it another way-

if len(my_list) == 1:
    power_set(my_list[1:]) == []

So it moves forwards because you hit the base case.

1 Like

As an Electrical Engineer, the iterative solution that uses binary digits to map to the power set is much more intuitive and easily understandable. It’s not at all complicated if you understand what’s going on.

The recursive solution is still a mystery to me.

Iterative solution using binary digit mapping

power_set = ['a', 'b', 'c']

‘a’ → position 1
‘b’ → position 2
‘c’ → position 3

1 → ON switch; 0 → OFF switch

000 → []
001 → ['c']
010 → ['b']
011 → ['b', 'c']
100 → ['a']
101 → ['a', 'c']
110 → ['a', 'b']
111 → ['a', 'b', 'c']

Think of the binary digits as ON/OFF switches. Now, map them onto the power set. You need as many switches as the number of items in the power set.

power_set = ['a', 'b', 'c']

‘a’ → position 1
‘b’ → position 2
‘c’ → position 3

1 → ON switch; 0 → OFF switch

000 → []
001 → ['c']
010 → ['b']
011 → ['b', 'c']
100 → ['a']
101 → ['a', 'c']
110 → ['a', 'b']
111 → ['a', 'b', 'c']