OOP question in python

can someone please explain to me what is going on here

class py_solution:

def sub_sets(self, sset):

    return self.subsetsRecur([], sorted(sset))



def subsetsRecur(self, current, sset):

    if sset:

        return self.subsetsRecur(current, sset[1:]) + self.subsetsRecur(current + [sset[0]], sset[1:])

    return [current]

print(py_solution().sub_sets([4,5,6]))

many thanks

It’s recursively creating a list of lists containing all different possible combinations of the original list. Also not related to OOP, as it can be done with basic functions.

For better understanding add some print-statements to see the internal steps taken (this is not OOP but same functions):

def sub_sets(sset):
    return subsetsRecur([], sorted(sset))

def subsetsRecur(current, sset):
    print(current,"\t|", sset)
    if sset:
        return subsetsRecur(current, sset[1:]) + subsetsRecur(current + [sset[0]], sset[1:])
    print("adding\t|", current)
    return [current]

print("final results:", sub_sets([1,2,3]))

Will produce:

[] 	| [1, 2, 3]
[] 	| [2, 3]
[] 	| [3]
[] 	| []
adding	| []
[3] 	| []
adding	| [3]
[2] 	| [3]
[2] 	| []
adding	| [2]
[2, 3] 	| []
adding	| [2, 3]
[1] 	| [2, 3]
[1] 	| [3]
[1] 	| []
adding	| [1]
[1, 3] 	| []
adding	| [1, 3]
[1, 2] 	| [3]
[1, 2] 	| []
adding	| [1, 2]
[1, 2, 3] 	| []
adding	| [1, 2, 3]
final results: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
1 Like
  1. here they are calling the function twice if am right, what the the right side of the addition doing and the left side?
  2. What is the base case here also

Am really struggling to understand recursion

Thanks

Jagmeet,
What is happening is that the subset here are being ‘added’ together and the result is being returned. In Python, adding 2 lists results in a single list with all elements from each list, so the return is a concatenation of both lists.

  1. The first element (left side of the first +) is the result of calling this same function, but with sset having the first element stripped off.
  2. The second element (right side of the first +) is the result of calling this same function but current having that stripped off element from before added to its members, and sset being the passed in sset with its first member stripped off again.

Basically like saying "OK, you gave me ([A, B] and [C, D]), so I am going to figure that out but showing you the result for ([A, B] and [D]) and the result for ([A,B,C] and [D]).
The beauty of recursion is that you can do that as long as you know that eventually you will break the problem down into a simple (aka ‘base’) case (or set of base cases) that you know how to solve. In this case, the case case is when sset is empty (i.e. calling this function for ([A,B,C,D] and )), in which case, the current set (i.e., [A,B,C,D]) is returned and then the function that called this base case appends the results of the other parts to that list and returns that, etc.

I hope that helps.

1 Like

You mean in general? Then you should start with a simple one, that can also be done in a non-recursive way. Like a Countdown/Countup or something (there is one in the curriculum). For double-recursions there are the Fibonacci-numbers which will also show you how a recursion can explode → because a basic Fibonacci-recursion will quickly (with values like 50-60) take minutes and then hours to conclude.

For your questions, the double call is a short way to write this:

call1 = subsetsRecur(current, sset[1:])
call2 = subsetsRecur(current + [sset[0]], sset[1:])
return call1 + call2

Reason is, once a function is called, the caller “waits” for it’s answer. In a recursion that calls itself several times, this creates a “stack” of functions, each waiting for the answer of the next one.
In this case, once the base-case is hit, where sset is an empty list, which is falsy in Python (meaning an if-statement will evaluate it as false) the function “return current”, which was passed by the previous caller. That caller then has call1 concluded and starts call2, which again stacks recursions…

And only when in a function both calls are completed, will it actually “add” them and adding lists in Python concatenates them.

so first call 1 is run then call 2 is run and the results are added or both are happening at the same time

Nothing happens “at the same time” in programming, until you start working with multithreading and multiprocessing :wink:
So yeah, it does call1 first and doesn’t touch call2 until call1 actually is returned with a result.

how do we know when the pop off will happen, and on the previous call stack l see that the calculations continue sometimes and sometimes the popping off happens, like l can’t even predict what is going to happen, because l don’t understand step by step what is going on till the end

I think l need a very detailed explanation to understand this

Thanks

Then go ahead an look at an easier recursion to start getting a feel for it.

For this, you can also add an argument to the recursion and print that, to see if the first or second call is happening.

def subsetsRecur(current, sset, call="start"):
print(call...)
...
subsetsRecur(..., call="first") + subsetsRecur(..., call="second")

ok that helps too, but how do you know when the pop off will happen.

Then it starts applying the code on a previous call stack/or the previous listings of the call stack(I don’t know the correct terminology, I hope you get me, like when you debug there is a call stack section on the left, l am using vs code, so it builds up a listing of stacks, then after that the popping off happens, I don’t know if am making myself clear

Thanks

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.