Why is my recursion leading to self referencing dict values?

Question

I aim to write a function that splits a budget across options by comparing options based on their benefit/cost ratio and stores them in a list of nested dicts. When multiple options with the same benefit/cost ratio are available, each option shall be pursued separately (as downstream element which in turn may have multiple downstream elements) and reflected as a list of dicts for its upstream dict. There is no limitation as to how many options may occur.

def get_all_allocation_proposals(budget, options, upstream_element=dict()):
    # accepts:
    #   budget to be allocated
    #   list of options
    # returns:
    #   a list of allocation proposals

    # filter options for affordable options and sort by cost benefit ratio
    options = [x for x in options if x['cost'] <= budget]
    options = sorted(options, key=lambda x: (
        x['benefit_cost_ratio'], x['benefit']), reverse=True)

    if (len(options) > 0):
        # select the best options
        best_bc_ratio = options[0]['benefit_cost_ratio']
        best_options = [
            x for x in options if x['benefit_cost_ratio'] == best_bc_ratio]
        upstream_element['downstream_elements'] = []

        for current_element in best_options:

            downstream_options = remove_conflicting_options(
                current_element, options)
            downstream_budget = budget - current_element['cost']
            current_element['donstream_budget'] = downstream_budget

            downstream_elements = get_all_allocation_proposals(downstream_budget,
                                                               downstream_options,
                                                               current_element)
            if downstream_elements is not None:
                current_element['downstream_elements'] = downstream_elements

            upstream_element['downstream_elements'].append(current_element)

        return upstream_element
    else:
        return None

In the code above, when the elements are appended, self referencing dict values are created. Why is that the case and how can I avoid that? All I want to do is to pass on all downstream elements to the first call stack. Is there something fundamentally flawed with my recursion pattern?

You would probably get more answers if you pared down the code to the absolute minimum required to reproduce the problem. Having said that, my guess is that you are falling into the "mutable default argument" trap: https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument — Ture Pålsson, Jan 28 '20 at 12:26

Simon Notley · Accepted Answer · 2020-01-28T13:07:51.813

I think the issue is probably because you are passing mutable objects into your recursive call. Specifically downstream_options and current_element are dicts and when you modify them within a given recursion of the function, you are also modifying them at the level above, which in this case seems to leave you attempting to assign a value in the dict to itself (or some such impossibility, I haven't quite managed to follow the logic through).

A quick solution might be (I'm not sure if this will break your logic) to make a copy of these dicts at each recursion:

from copy import deepcopy

...

downstream_elements = get_all_allocation_proposals(downstream_budget,
                                                   deepcopy(downstream_options),
                                                   deepcopy(current_element))

Additionally, as identified in the comments you should avoid having a mutable default argument, i.e. upstream_element=dict(). This can produce some very confusing behaviour if you actually use the default (which you don't appear to in your code)

Why is my recursion leading to self referencing dict values?

1 Answers1