What does this code mean (if v then return v end)?

Question

So I have this piece of code and it is this:

do 

    local function index(n,m)
        return n*(n+1)//2 + m
    end

    local binomtable = {}

    function binom3(n,m)
        if n<0 or m<0 or m>n then return 0 end
        if n=0 or m=0 or m=n then return 1 end
        local i = index(n,m)
        local v = binomtable[i]
        if v then return v end
        v = binom3(n-1,m-1) + binom3(n-1,m)
        binomtable[i] = v
        return v
    end

end

and I would like to know what

if v then return v end

means.

Thank you!

Answer 1

The short answer is that if v then return v end returns the value v if it is truthy, i.e., if it is neither false nor nil. Otherwise the function continues by calculating a value for v, storing that value in binomtable, and finally returning it. The more interesting question is, why is the function doing all of this?

In the posted code, binom3 is a recursive function. With the recursive calls v = binom3(n-1,m-1) + binom3(n-1,m) there will be a lot of duplication of effort, meaning a lot of wasted space and time. Consider:

binom3(4, 2)
--> binom3(3, 1) + binom3(3, 2)
--> binom3(2, 0) + binom3(2, 1) + binom3(2, 1) + binom3(2, 2)
--> 1 + binom3(1, 0) + binom3(1, 1) + binom3(1, 0) + binom3(1, 1) + 1

Note how in the second reduction there are two identical terms:

binom3(2, 1) + binom3(2, 1)

There is no reason to calculate the term binom3(2, 1) twice, and doing so means that the pair of terms:

binom3(1, 0) + binom3(1, 1)

also must be calculated twice, as seen in the third reduction. It would be smart to calculate binom3(2, 1) only once, and to save the result for later use in the larger calculation. When m and n are larger and the number of calculations explodes exponentially this becomes a very important issue for performance both in the amount of memory required and in the amount of time required.

The posted code is using memoization to improve performance. When a calculation is made, it is stored in the table binomtable. Before any calculation is made, binomtable is consulted. First, v is set to the value of binomtable[i]; if this value is any truthy value (any integer is a truthy in Lua), then that value is simply returned without the need for recursive calculation. Otherwise, if nil is returned (i.e., no value has yet been stored for the calculation), the function continues with a recursive calculation. After completing the calculation, the new value is stored in binomtable for use the next time it is needed. This strategy saves a lot of wasted computational effort, and can make a huge difference in the performance of such recursive algorithms.