# what does it mean if v is returned then v ends?

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.

CLICK HERE to find out more related problems solutions.

Scroll to Top