Functional Python : Recursion

So what is pres referring to.... is that just a bastardized way of being lazy and not wrtiting out prerequisites... if not I really have no clue as to what this function is doing. That assuming that prereqs() is taking courses for data and any prerequisites already know for arguments

Hi Chris,

For this ancient question please indulge a new-comer a question about this:

Since in each recursive call, the local pres value is returned but not received by any name of the outer call, how did the outer-most finally pres get all the added value?

For the outer-most function, the only time pres gets assigned is at the empty set.

Good question Richard Li!

Python passes references to objects when calling functions. So this call:

        prereqs(prereq, pres)

is calling prereqs to find the subsequent prerequisites with the for loop variable prereq and passing the reference to the object pres.

Since the reference pres points to the same object as the in the top level call to the function preteqs, all recursive executions of the line:

        pres.add(prereq[‘title’])

modifes the same pres object! When all the recursion is complete, the top level reference to pres will also have all the added titles. Very cool!

Post back if you need more help. Good luck!!!

Thanks Kenneth for the Labor Day help. I think there might still be some confusion. Looking at the new prompt

"Finish the prereqs function so that it recursively finds all of the prerequisite course titles in courses (like "Object-Oriented Python" is a prerequisite for "Django Basics"). You should add() the title to the pres set and then call prereqs again with the child courses. In the end, return the prereqs set."

The last sentence, if read on its own, could still be misread as: "You should add() the [top course] title to the pres set and then call prereqs again...."

If I could suggest one more tweak:

"You should add() the [prerequisite] title to the pres set and then call prereqs again ....", or

"[For each prerequisite y]ou should add() the title to the pres set and then call prereqs again...."

Thanks, Chris "The Overly Analytical"

Done.

You are the Best!

The function gets a dictionary of courses, some of which have prerequisites. The function needs to return a set of all of the prerequisites. You have to do this in a recursive manner. data would be all of the courses, pres is the current set of prerequisites.

I think "it failed this condition" is not precise, because statement

pres = pres or set()

never fails, it just choose from the value which is not empty. So when you choose from pres = set() or set(), it wouldn't return the set you pass into this function as argument.

Uh, what? Set is not deprecated at all and likely never will be.

The method append() is used for lists. In this code we are using sets which do not have an append method:

>>> s = set()
>>> s.append("foo")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'append'

See "help(set)" or the docs

pres is an argument to the function. set is a data type, like list, and you can create one by using the set() function, like you would with lists or strings or dicts.

sets have a method named add that adds things to the set.

Well, it's a common word, especially in programming. It's a data structure, it's an action ("set the variable to 5"), it's likely a method on some class or other. One of the challenges of tying programming languages to spoken languages, I guess.

Reading your comments, I think you need to take a step back from this challenge and look at it from another angle. It's a recursive challenge, so the function is going to be called again and again with, ideally, smaller and smaller sets (ha!) of data. Ignore all of that. How would you solve this with for loops and ifs?

Richard Li, it is because pres's reference is passed into each call. So, inside each recursive call, each update is effectively applied to the outer pres. The exception is when the inner pres is re-assigned to a new set based on the pres = pres or set() condition check ... then the outer pres won't be updated inside the function, because the reference to it is no longer to the outer pres. (See my comment above.)

It is misleading to use the phrase “call by value” as this does not happen in Python. Python passes references to objects.

Because a reference to the current pres is passed into each recursion. The recursive modifications all operate on the same object.

Because of the passed pres references, the return pres is not needed during recursion. The return is only needed when the recursion is finished and the top level exits. This final return is what sends back the solution reference to the original calling statement.

Since all the recursive calls include a pres argument, the pres = pres or set() would only create a new set at the top-level call to prereqs and never during an inner iteration.

Richard Li, it is because pres's reference is passed into each call by value. So, inside each recursive call, each update is effectively applied to the outer pres. The exception is when the inner pres is re-assigned to a new set based on the pres = pres or set() condition check ... then the outer pres won't be updated inside the function, because the reference to it is no longer to the outer pres. (See my comment above.)

Chris,

Thanks ... what I meant is that references are passed by value for each call of the function, that is, a copy of the reference value is passed into the function. That's why when the local variable is reassigned to a different object, the global variable is not affected.

Effectively, (quoting Python parameter passing )

This means that Python initially behaves like call-by-reference, but as soon as we are changing the value of such a variable, Python "switches" to call-by-value.

But I can see how my original wording could be confusing, as it has the awkward phrasing "call by value," which taken out of context can be misleading, as you said. I'll edit my original comment to clarify, thanks.

I apologize if I’m be overly specific. There isn’t any actual call-by-value. Python will seem to behave as a call-by-value when a global value or parameter is assigned to. It is this assignment to a variable of the same name as a parameter or global value that creates this local variable of the same name thereby protecting the global object from being overwritten.

Note that modifying a passed in object is not creating anything, so it’s the global or passed in object is modified.

Since this code only modifies the pres set, the global object is changed and no new local object is created.

Looking at the following code. It prints the value and ID of the passed values. Note it is at the increment when the local variable gets created and the object passed in isn’t affected by the increment (notice the new id value). The append modifies param2 so no new local object is created.

def func(param1, param2):
    print("2: ", param1, id(param1) , param2, id(param2))
    param1 += 1
    param2.append(param1)
    print("3: ", param1, id(param1) , param2, id(param2))

value1 = 6
value2 = []
print('1: ', value1, id(value1), value2, id(value2))
func(value1, value2)
print('4: ', value1, id(value1), value2, id(value2))

value1 += 10 

print('5: ', value1, id(value1), value2, id(value2))
func(value1, value2)
print('6: ', value1, id(value1), value2, id(value2))

# produces the output:
# 1:  60 4385563008 [] 4693608776
# 2:  60 4385563008 [] 4693608776
# 3:  61 4385563040 [61] 4693608776
# 4:  60 4385563008 [61] 4693608776
# 5:  70 4385563328 [61] 4693608776
# 2:  70 4385563328 [61] 4693608776
# 3:  71 4385563360 [61, 71] 4693608776
# 6:  70 4385563328 [61, 71] 4693608776

Chris Freeman and David Lin@davejlin

Thank you so so much!! I now have a better understanding on the python recursion. It's like passing a pointer of the original set and all the appendings are happening at the same place.

Good question! The challenge wording asks you to find “finds all of the prerequisite course titles in courses”, meaning all courses that are a prerequisite of another course. While “Django Basics” has prerequisites, itself is not a prerequisite of another course.

Post back if you need more help. Good luck!!!

@chrisfreeman3 aha! I see. I got what you mean! Thanks