Default dictionary parameter in recursive function

Question

def fib(n, fib_vals={}):
    if fib_vals.get(n):
        return fib_vals[n]

    if n <= 1:
        return n

    fib_vals[n] = fib(n - 1) + fib(n - 2)
    return fib_vals[n]


if __name__ == '__main__':
    print(fib(900))

I was running the code above and it was working just fine. Then I realized that I wasn't passing the fib_vals dictionary in my recursive calls. How is this even working?

See [this](https://docs.python-guide.org/writing/gotchas/#mutable-default-arguments) — Yevhen Kuzmovych, Jul 20 '21 at 16:47
Where you have this: `def fib(n, fib_vals={}):` you have a definition of `fib_vals`, that is to say it has a default value which means that you don't have to supply one in any call to `fib()`. — quamrana, Jul 20 '21 at 16:48
the first line of your code jumps to the eye: **do not use mutable arguments**, as @YevhenKuzmovych rightly pointed out. — Pierre D, Jul 20 '21 at 17:00
@PierreD: well although this is a default mutable argument, it works in this case. — quamrana, Jul 20 '21 at 17:06
@PierreD well, in this case, that serves a point. It's memoization — juanpa.arrivillaga, Jul 20 '21 at 17:57
@juanpa.arrivillaga: yes, obviously, but then use [`@cache`](https://docs.python.org/3/library/functools.html#functools.cache) or `@lru_cache`. I have wasted too many cycles debugging functions where people used mutable defaults. These days, I make sure I don't let folks disable [PyLint's W0102](http://pylint-messages.wikidot.com/messages:w0102) in our CI. — Pierre D, Jul 20 '21 at 19:24

score 1 · Accepted Answer · 2021-07-21T06:35:23.393

When fib() is called without the second parameter, the Python interpreter will instantiate an empty dictionary referenced by fib_vals. That dictionary is, effectively, persistent between similar invocations of fib().

In order to understand what's going on, it might help you to change your code (purely for demonstration purposes) thus:

FV = {}
def fib(n, fib_vals={}):
    global FV
    FV = fib_vals
    if fib_vals.get(n):
        return fib_vals[n]

    if n <= 1:
        return n

    fib_vals[n] = fib(n - 1) + fib(n - 2)
    return fib_vals[n]


if __name__ == '__main__':
    print(fib(10))
    print(FV)
    print(fib(9))
    print(FV)

You will notice that the value of FV doesn't change. It will change if/when fib() is invoked with a higher value for the first parameter.

EDIT: Correction: fib_vals is instantiated when fib() is parsed by the Python interpreter and not when fib() is first called.

btw, the empty `dict` is instantiated when `fib()` is declared, not when `fib()` is called. That's why it is persistent across many calls. — quamrana, Jul 20 '21 at 17:04
You're quite certain it's instantiated on first call, not during the function's declaration? — Charles Duffy, Jul 20 '21 at 17:11

Default dictionary parameter in recursive function

1 Answers1