How can I calculate the number of times a specific function will get executed in recursion?

Question

This question is in reference to below code:

cost = [[1, 10, 75, 92],
         [-1, 0, 35, 50],
         [-1, -1, 0, 80],
         [-1, -1, -1, 0]]

def min_cost(source, destination):
   if s==d or s == d-1:
       return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
return mc

When I did a dry run of the same I saw min_cost(1,3) is getting executed two times. I read in one book where the author mentioned if we had 10 stations in between, then min_cost(1, 3) would run 144 times.

How can we figure out these numbers without actually doing a dry run? I know using recursion equations we can figure out the time taken by the function, but how can we say that a specific function will be executed this many number of times?

Answer 1

While I understand that you don't want a dry run to just count the calls, I'd like to nevertheless do it first, just to see what's going on. So, here goes:

def min_cost(s, d):
    global count
    count += 1
    if s==d or s == d-1:
        return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
    return mc

for n in range (2, 8):
    cost = [[0 for i in range (n)] for j in range (n)]
    count = 0
    min_cost(0, n-1)
    print (str (n) + ': ' + str (count))

The output is:

2: 1
3: 3
4: 9
5: 27
6: 81
7: 243

So, we see that the number of calls for d-s=k is 3 to the power of (k-1). Knowing what we have to prove sometimes greatly simplifies finding the proof.

---

Now, to the proof itself. It will be proof by induction. First, note that the number of calls of min_cost(s, d) depends only on the value of d-s, and not on the individual values of s and d.

The base is that, for d-s=1, we get one call. For d-s>1, we make our one call, and from it the following calls:

min_cost(s, s+1) and min_cost(s+1, d)
min_cost(s, s+2) and min_cost(s+2, d)
...
min_cost(s, d-1) and min_cost(d-1, d)

So, for d-s=k, the number of calls f(k) is:

f(k) = 1 +
       f(1) + f(k-1) +
       f(2) + f(k-2) +
       ... +
       f(k-1) + f(1)
     = 2 * (f(1) + f(2) + ... + f(k-1))

If, by the induction hypothesis, we have already proved that f(v) = 3^v for all v < k, then the f(k) is:
1 + 2 * (3¹ + 3² + ... + 3^k-1), which is trivially 3^k, completing our proof.

---

Lastly, note that, while the presented algorithm is exponential, the underlying problem can be solved in polynomial time, most simply in O((d-s)^2) by memoizing the calls for which we already did all the work.

Answer 2

There are several options to calculate that amount when one is working with recursion. The simplest would be to add another variable to the recursive method which is increased every time it gets recursed and in the last statement where it is returned it does not increment, but just return the last amount, which will recursive 'back' to the upper request.

Example in pseudo code:

function recursionfunction(x, y, recursioncount) {
    if(expressionIsFalse) {
        recursionfunction(x, y, recursioncount+1);
    } else {
        return recursioncount;
    }
}

print recursionfunction('','', 0);

Another way of working is assigning a variable by reference, a pointer or a global variable (depending on the programming language) and incrementing that counter.

Did this help you?