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

Answer 1

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.