CODEWITHSUNDEEP
pythonif-statementrecursion
a_r
a_r

Reputation: 518

Why removing else causes recursive function to repeat the result?

When I execute the following code on Python console using the below statement,

for L in permute([12, 32, 3]):
    print(L)

for the code below, 

def permute(L):
    if len(L) <= 1:
        yield L
    else:
        for i in range(0, len(L)):
            L[0], L[i] = L[i], L[0]
            for L1 in permute(L[1:]):
                yield [L[0]] + L1

each result appears just once. But, if I remove else and remove the associated indentation of the code below it, I receive each result twice. Why does it happen?

Upvotes: 1

Views: 84

Answers (2)

Azat Ibrakov
Azat Ibrakov

Reputation: 10990

From docs:

The big difference between yield and a return statement is that on reaching a yield the generator’s state of execution is suspended and local variables are preserved. On the next call to the generator’s __next__() method, the function will resume executing.

So this happens because if body doesn't break execution, so it moves forward to the next yield statement and with else clause reaches end of function and implicitly returns.

Check

def counter(step):
    assert step >= 0, ('Can count only from non-negative number, but found '
                       + str(step))
    if step == 0:
        print('Reached end')
        yield step
    print('Step', step)
    for sub_step in counter(step - 1):
        yield sub_step

>>> list(counter(1))

Step 1
Reached end
Traceback (most recent call last):
  File "<input>", line 13, in <module>
Step 0
  File "<input>", line 8, in counter
  File "<input>", line 8, in counter
  File "<input>", line 3, in counter
AssertionError: Can count only from non-negative number, but found -1

and

def counter(step):
    assert step >= 0, ('Can count only from non-negative number, but found '
                       + str(step))
    if step == 0:
        print('Reached end')
        yield step
    else:
        print('Step', step)
        for sub_step in counter(step - 1):
            yield sub_step
    # implicitly returns here

>>> list(counter(1))
Step 1
Reached end

As we can see without else execution will continue and call counter with step equal to -1.

So you can leave else or refactor your if clause and add return statement into it to explicitly finish execution like

def permute(L):
    if len(L) <= 1:
        yield L
        return
    for i in range(0, len(L)):
        L[0], L[i] = L[i], L[0]
        for L1 in permute(L[1:]):
            yield [L[0]] + L1

Further reading

Upvotes: 1

akshat
akshat

Reputation: 1217

Because you are yielding twice, if there is no else loop.

Upvotes: 0

Related Questions