Why is my recursive function updating a list (calculating fibonacci of n)

Question

I'm trying to learn about dynamic programming. I've gone through an example of how to find the Fibonacci number of an inputn, while caching the result of each "new" call as I go.

I understand the order in which the function recursively calls: fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1) -> fib(0) -> fib(1) -> fib(2) "Cache found" -> fib(3) "Cache found" for n = 5

I'm struggling to understand how the final fib(2) and fib(3) calls have access to the updated cache, as each call only returns an integer, not the list, and I don't think I have the list declared as a global variable.

I originally expected the list to behave like the integer x in my code, so would welcome explanations for how the values have been passed back up.

Code:

def fib(n, cache, x):
    print(n, cache)
    print("x: ", x)
    x += 1
    if n == 0 or n == 1:
        return n

    if cache[n] == 0:
        cache[n] = fib(n-1, cache, x) + fib(n-2, cache, x)
    else:
        print("Cache called on", n)

    return cache[n]


def main():
    n = 5
    x = 0
    cache = [0 for _ in range(n+1)]
    print(fib(n, cache, x))
    print(cache)
    print("x: ", x)


if __name__ == "__main__":
    main()

Output:

5 [0, 0, 0, 0, 0, 0]
x:  0
4 [0, 0, 0, 0, 0, 0]
x:  1
3 [0, 0, 0, 0, 0, 0]
x:  2
2 [0, 0, 0, 0, 0, 0]
x:  3
1 [0, 0, 0, 0, 0, 0]
x:  4
0 [0, 0, 0, 0, 0, 0]
x:  4
1 [0, 0, 1, 0, 0, 0]
x:  3
2 [0, 0, 1, 2, 0, 0]
x:  2
Cache called on 2
3 [0, 0, 1, 2, 3, 0]
x:  1
Cache called on 3
5
[0, 0, 1, 2, 3, 5]
x:  0

This sounds like a good time to read about how [Python variables and objects work](https://nedbatchelder.com/text/names.html). — user2357112, Aug 15 '18 at 17:58
You are passing the list as an argument all along, so it is wrong to say that function do not have access to it. — Olivier Melançon, Aug 15 '18 at 18:00

score 1 · Answer 1 · answered Aug 15 '18 at 18:00

1

You passed the original of cache, rather than a copy (newly-built object). Thus, each instance of fib is working with the same object. An update in one instance is immediately available to the others. See also here.

answered Aug 15 '18 at 18:00

Prune

76,765
14
60
81

haccks · Accepted Answer · 2018-08-15T18:50:34.393

In python function arguments are "passed-by-object" (or pass-by-object-reference). It means that if you pass the list (a mutable object) to a function then elements of the list can be modified. But if you will assign the list by a new list then the list will not change in the caller's scope.

def list_scope(l):
    print(l, "id: ", id(l))
    l = [3, 4,5]
    print(l, "id: ", id(l))

def main():
    l = [1, 2, 3]
    print("id: ", id(l))
    list_scope(l)
    print("id: ", id(l))

main()

Output:

id: 4510275784
[1, 2, 3] id:  4510275784
[3, 4, 5] id:  4509275592
id: 4510275784

The id for l in list_scope before assigning list [3, 4, 5] is same as the id in main. It changes once [3, 4, 5] is assigned, but remain same in main.

Why is my recursive function updating a list (calculating fibonacci of n)

2 Answers2