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

Question

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

I have tested with yield too. Didn't paste that code as I was debugging and had updated the code. but, essentially I tested it with print, as well as yield in both functions at the line where we have print(num) — Naman Bhalla, Aug 23 '18 at 18:00
And every time you use `yield` instead of `print`, there's no output, yes? — Aran-Fey, Aug 23 '18 at 18:01
Thanks @Aran-Fey I was able to understand the mistake in my code because of the hint you provided. For future reference, the issue was that the recursive code was yielding values and I am not yielding those. After your hint, I checked https://stackoverflow.com/questions/8991840/recursion-using-yield and was able to solve. Thanks. — Naman Bhalla, Aug 23 '18 at 18:09

score 1 · Accepted Answer · answered Aug 23 '18 at 18:43

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)

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

1 Answers1

Python 2