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. — user2357112
– user2357112, Commented Aug 15, 2018 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
– Olivier Melançon, Commented Aug 15, 2018 at 18:00

haccks · Accepted Answer · 2018-08-15 18:50:34Z

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.

edited Aug 15, 2018 at 18:50

answered Aug 15, 2018 at 18:07

haccks

107k28 gold badges181 silver badges274 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Prune · Accepted Answer · 2018-08-15 18:00:35Z

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, 2018 at 18:00

Prune

78k14 gold badges63 silver badges83 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related