Recursion step doesn't update output-CodePudding

I have a problem with the recursion. The function I wrote should recursively generate and return a list of pairs, called chain. The breaking condition is when the pair, (remainder, quotient) already belongs to the chain-list, then stop iterating and return the list. Instead of completing, the recursion just blows up, raising a RecursionError. The list doesn't update and contains only a single term, so the breaking condition is not executed. I don't understand why...

How should I proper implement the recursive step to make the list update?

def proper_long_division(a, b):
    """a < b"""
    chain = []

    block_size = len(str(b)) - len(str(a))

    a_new_str = str(a)   '0' * block_size
    a_new = int(a_new_str)
    if a_new < b:
        a_new = int(a_new_str   '0')

    quotient = a_new // b
    remainder = a_new - b * quotient

    print(remainder)    
    #print(chain)
    
    # breaking condition <--- ! 
    if (remainder, quotient) in chain:
        return chain

    # next step
    chain.append((remainder, quotient))
    chain.extend(proper_long_division(remainder, b))
 
    return chain

try:
    a = proper_long_division(78, 91)    
    print(a)
except RecursionError:
    print('boom')

Here a an example of recursion which (should) follows the same structure but the returned list is updated. I don't know why one code works while the other does not.

import random

random.seed(1701)

def recursion():
    nrs = []
    # breaking condition
    if (r := random.random()) > .5:
        return nrs
    # update
    nrs.append(r)
    # recursive step
    nrs.extend(recursion())
    return nrs

a = recursion()
print(a)
# [0.4919374389681155, 0.4654907396198952]

CodePudding user response：

When you enter proper_long_division, the first thing you do is chain = []. That means that the local variable chain refers to a new empty list. Then you do some algebra, which does not affect chain, and check if (remainder, quotient) in chain:. Clearly this will always be False, since chain was and has remained empty.

The next line, chain.append((remainder, quotient)) runs just fine, but remember that only this call to proper_long_division has a reference to it.

Now you call chain.extend(proper_long_division(remainder, b)). You seem to expect that the recursive call will be able to check and modify chain. However, the object referred to by chain in a given call of proper_long_division is only visible within that call.

To fix that, you can use a piece of shared memory that any invocation of the recursive function can see. You could use a global variable, but that would make the function have unpredictable behavior since anyone could modify the list. A better way would be to use a nested function that has access to a list in the enclosing scope:

def proper_long_division(a, b):
    """a < b"""
    chain = {}

    def nested(a, b):
        while a < b:
            a *= 10
        quotient = a // b
        remainder = a - b * quotient

        key = (remainder, quotient)
        if key in chain:
            return chain

        # next step
        chain[key] = None
        nested(remainder, b)
 
    nested(a, b)
    return list(chain.keys())

A couple of suggested changes are showcased above. Multiplication by 10 is the same as padding with a zero to the right, so you don't need to play games with strings. Lookup in a hashtable is much faster than a list. Since ordering is important, you can't use a set. Instead, I turned chain into a dict, which is ordered as of python 3.6, and used only the keys for lookup. The values all refer to the singleton None.

The second example does not match the structure of the first in the one way that matters: you do not use nrs as part of your exit criterion.