CODEWITHSUNDEEP
pythonpython-3.x
Naman Bhalla
Naman Bhalla

Reputation: 48

Recursion not happening in a Class unless I use a helper method

I was coding the dfs solution for a problem.

When I write the code as below, on debugging, I find that whenever the code reaches at self.dfs_solution_rework, instead of recursing, it just continues execution, leading to wrong results.:

def dfs_solution_rework(self, end, start= 1, sorted=False, num= None):
    if not num:
        for i in range(1, 10):
            self.dfs_solution_rework(end, start, num=i)
    elif num <= end:
        if num >= start:
            yield num
        last_digit = num % 10
        if not (last_digit == 0 or last_digit == 9):
            self.dfs_solution_rework(end, start, num=num * 10 + (last_digit - 1))
            self.dfs_solution_rework(end, start, num=num * 10 + (last_digit + 1))
        elif last_digit == 0:
            self.dfs_solution_rework(end, start, num=num * 10 + 1)
        else:
            self.dfs_solution_rework(end, start, num=num * 10 + 8)

On the other hand, if I write the dfs with a util (helper) method, as follows, it works without any issues. 

def dfs_solution(self, end, start= 1, sorted=False, num= None):
    def dfs_util(end, start, num):
        if num <= end:
            if num >= start:
                print(num)
            last_digit = num % 10
            if not (last_digit == 0 or last_digit == 9):
                dfs_util(end, start, num=num * 10 + (last_digit - 1))
                dfs_util(end, start, num=num * 10 + (last_digit + 1))
            elif last_digit == 0:
                dfs_util(end, start, num=num * 10 + 1)
            else:
                dfs_util(end, start, num=num * 10 + 8)

    for i in range(1, 10):
        dfs_util(end, start, num=i)

Any help as to why this behaviour might be happening ? I have debugged it in VS Code to understand but couldn't get any idea.

PS: Not a homework problem. :)

Thanks

Upvotes: 0

Views: 41

Answers (1)

zvone
zvone

Reputation: 19362

A recursive generator needs to yield the results of the recursion.

A simplified example with the same problem as yours would be this recursive counter:

def count_to_zero(n):
    yield n
    if n == 0:
        return
    count_to_zero(n-1)

It only yields one value: n. That is because the recursion call to count_to_zero(n-1) just created a generator which was never consumed.

Test:

>>> print(list(count_to_zero(5)))
[5]

The solution here would be:

def count_to_zero(n):
    yield n
    if n == 0:
        return
    yield from count_to_zero(n-1)

Test:

>>> print(list(count_to_zero(5)))
[5, 4, 3, 2, 1, 0]

The same needs to be done in your example as well, for every recursive call to self.dfs_solution_rework, e.g.

 yield from self.dfs_solution_rework(end, start, num=num * 10 + 1)

Python 2

As a side note, notice that this syntax does not work in Python 2. There one would have to do:

for result in count_to_zero(n-1):
    yield result

which is the same as:

yield from count_to_zero(n-1)

Upvotes: 1

Related Questions