# 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.

20 Likes

Thank you. This is very helpful.

What I am wondering, and where I am struggling to under stand is, how does the function calls itself again? Because in all the exercises before, in the return statement, we somehow called the function again, giving it a modified parameter. But here it just says return, and I don’t know how the function knows to call itself again with these parameters, instead of just exiting the function and return the wf and pswf.
If someone could help me with that, that would be awesome!!!

3 Likes

One clarification needed. Your abbreviation wf stands for “without_first” or “with_first”?

2 Likes

The recursive call is in the beginning.

power_set_without_first = power_set(my_list[1:])

Here the same function is called again with a truncated list (the original list minus the first element). This introduces a loose thread, where the same list is called again with one less element.

To understand what this returns, for me it helps to think back all the way from the base case, in this case a list where all original elements have been removed. This returns empty and then all loose threads that have been created can be wrapped up.
If you closely examine the result, you can actually see this happening. All the elements at the bottom, are repeated above, in the same order, but with the first element added back on. This is repeated until you have the original list all the way at the top.

Hope this helps!

Found this description in a youtube video and found it helpful - hopefully, it helps anyone reading. This exercise was fun! Complicated but fun!

I think I finally understand recursion…

Normally when recursion is taught they simply say, “first create your base step, this ends the recursion, then create your recursive step here the function calls itself and solves the problem recursively”. Most resources I have found don’t really elaborate on the thought process rather they elaborate on what is happening at a lower level (stack, etc).

Through this video I have found that recursion can actually be broken down into three steps:

1. The base step (stops recursion)
2. The Minimization step (creates the smallest possible instance of a problem. Example: 500 element array turned into 1 or 2 element array)
3. The Solution step (This handles the solution for the 1 or 2 element array rather then the 500 elements)

Once the function arrives at the Solution step, the array has already been broken down to its smallest possible version. It then solves the smallest problem and works its way up solving and handling the rest of the array.

This is extremely helpful. I was stuck on trying to understand how to obtain the middle values by themselves, e.g. [‘STANFORD’], [‘UCLA’], etc. Turns out I was missing out on the [empty]. I was stuck here for more than half an hour, and was so ready to give up. Thank you so much for typing this out!

1 Like

I spent some time trying to understand on a deeper level exactly how this works. Some of the posts above definitely helped, but I felt like I wanted a more fundamental understanding of the mechanics so I dug deeper. I would have liked, more than just about anything to this point in the course (and frankly out of any of the “Python 3” courses as well, up through advanced), for this to have a thorough explanation within the lesson. It’s too bad it was essentially glossed over, despite the fact that, at least for me, the iterative version (above in the same lesson) was much easier to fully wrap my mind around.

This is different than other basic recursive problems given imo, to this point, in that the recursive “wind up” and “unwinding” don’t all happen within the return statement itself (such as with something like the factorial recursive function). Here the recursive call is near the top of the function (wind up), and the return is at the bottom (not referring to base case which essentially concludes the wind up itself). Anyway, the key to me is the whole idea of the call stack and especially how variables are saved within each call stack frame (not sure if the terminology is 100% correct here…still learning…but this concept was talked about in an earlier lesson). How my_list was handled was confusing to me initially, particularly once you call an empty list within the recursive wind up, until I thought more about these concepts and how the variables end up saved within the stack.

The unwinding then happens when the bottom return statement is reached, which then pops the call stack and, importantly, gives you access to the “prior” my_list element[0], allowing you to iterate through power_set_without_first and interact with its elements using the “next” my_list element[0] (the value returned to power_set_without_first is iterated over each time we unwind after it’s returned…which reminds me in a way of generator/yield statement behavior). Also, temporarily refactoring the list comprehension as an empty list assignment with a for loop and appending to that empty list, I think is also helpful to clarify steps happening.

This post may be dust in the wind at this point but if anyone is working on this problem currently and would appreciate more step-by-step on the actual code itself, or clarification on the above (don’t have too much time to shorten my post so hopefully it’s clear enough), lmk and I can go through my thought process with it. Anyway, hope this is helpful in adding to the discussion!

2 Likes

Hey there! Amazing thing, I struggled a bit tho because the order was different from the exercise, which returns 'wf+pswf" instead of ‘pswf+ wf’, definetly got my brain working for a bit.

Hi! Ty for the reply! Feels good to talk it through! I thought about this problem some more (I can’t help it I have to know how things are working like literally 100% which fortunately, this personality trait is good for coding ).

I realized most of my initial confusion was simply because I was thinking > function call > variable assignment > then confusion set in! Almost was looking at it like a decorated function for some reason haha. I knew variable assignment worked from right to left (expression evaluated first) but tbh combined with the recursion it threw me off. Obviously it’s just a series of (essentially) separate function calls and once you have a return, that particular variable in that “function instance” is assigned within the function it was called in. Hopefully that makes sense. Anyway, I think I basically understood things before but it feels good when you’re like…yeah I know all the steps without any doubts!

1 Like

I was really struggling with this one! Definitely needs more explanation please CC.

Here is a link to my worksheet breaking the problem’s solution down a little for others who come across this discussion as confused as I.