Newbie needs help to understand the Recursion in Python

Question

As the title suggested, i am still a newbie for programming and met this recursion algorithm and got stuck for 3-4 hours and still cannot figure out how the recursion works

The task is:(sorry for the picture rather than the text since they dont allow users to copy and paste)

The solution for this is:

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


    def branchSums(root):
        sums = []
        calculateBranchSums(root, 0, sums)
        return sums
    
    def calculateBranchSums(node, runningSum, sums):
        if node is None:
            return 
        newRunningSum = node.value + runningSum
        
        if node.left is None and node.right is None:
            sums.append(newRunningSum)
            return
        calculateBranchSums(node.left, newRunningSum, sums)
        calculateBranchSums(node.right, newRunningSum, sums)

I actually understand the logic here but I am really confuse on two points:

(1) when we use sums initially as a empty list to function calculateBranchSums, how does it modify the sums list without returning and reassigning to the sums;

(2) why all the return in calculateBranchSums function returns nothing;

Objects are passed by reference in python, so modifying them within a function will change the object passed in. — luthervespers, Nov 10 '20 at 02:17
@luthervespers **no python does not support call by reference at all** If it were, you could write a function like this `def foo(&x): x = 42; y = 0; foo(y); print(y)` and it would print `42`, but you can't (in the general case) — juanpa.arrivillaga, Nov 10 '20 at 02:18
To answer your second question, please see [this answer](https://stackoverflow.com/questions/15300550/return-return-none-and-no-return-at-all) — Boomer, Nov 10 '20 at 02:18
In any case, I think recursion is simply muddying the waters. Consider the following code: `def foo(data): data.append('foo')`, then try `x = []; foo(x); print(x)` and you will get `['foo']` — juanpa.arrivillaga, Nov 10 '20 at 02:21
I think this answer also help you. https://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference — Canasta, Nov 10 '20 at 02:22
@juanpa.arrivillaga you're right, scalar values are not passed by reference. Everything else is, but you don't need to dereference. — luthervespers, Nov 10 '20 at 02:30
@luthervespers **no**. Nothing is ever call by reference. It doesn't matter the type. Again, If python *did* support call by reference, you could do: `def foo(x): x = [42]` then `y = []; foo(y); print(y)` and it would print `[42]`. There is no distinction between "scalar" types. — juanpa.arrivillaga, Nov 10 '20 at 03:13

score 0 · Answer 1 · answered Nov 10 '20 at 02:10

0

In python, lists are passed by reference. This means, if you provide a list to a function, and the function mutates the list, the changes will be reflected outside the function:

def modify(lst):
    lst[0] = 1

myList = [4, 5, 6]
modify(myList)
myList # [1, 5, 6]

The function doesn't need to return anything, so the returns simply return nothing and only exist to exit the function early.

answered Nov 10 '20 at 02:10

Aplet123

33,825
1
29
55

lists are *not* passed by reference. Python uses a *single* evaluation strategy regardless of the type that is neither call by reference nor call by value. It is named "call by object sharing", but that is a rather obscure name. In the Java world, they sometimes say things like "it is call by value but all values are references", but IMO simply confuses the *implementation* for the semantics. More commonly you might hear that Python is "call by object reference". – juanpa.arrivillaga Nov 10 '20 at 02:17
1

Here is a good explanation of the distinctions: https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/ – juanpa.arrivillaga Nov 10 '20 at 02:17

Newbie needs help to understand the Recursion in Python

1 Answers1