# Recurrence relation for the number of “references” to two mutually recursive function

I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line scheduling

(Note: Assembly line scheduling or dynamic programming is not required to answer to the question though, it is just for information so that it shall help relating the context).

$$(1),(2),(3)$$ are three relations as shown.

$$f_{1}[j] = \begin{cases} e_1+a_{1,1} &\quad\text{if } j=1\\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if } j\geq2\\ \end{cases}\tag 1$$

Symmetrically,

$$f_{2}[j] = \begin{cases} e_2+a_{2,1} &\quad\text{if } j=1\\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if } j\geq2\\ \end{cases}\tag 2$$

(where $$e_i,a_{i,j},t_{2,j-1}$$ are constants for $$i=1,2$$ and $$j=1,2,3,...,n$$)

$$f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$$

The text tries to find the recurrence relation of the number of times $$f_i[j]$$ ($$i=1,2$$ and $$j=1,2,3,...,n$$) is referenced if we write a mutual recursive code for $$f_1[j]$$ and $$f_2[j]$$. Let $$r_i(j)$$ denote the number of times $$f_i[j]$$ is referenced.

They say that,

From $$(3)$$,

$$r_1(n)=r_2(n)=1.\tag4$$

From $$(1)$$ and $$(2)$$,

$$r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$$

I could not quite understand how the relations of $$(4)$$ and $$(5)$$ are obtained from the three corresponding relations. (directly without any proof, is it so trivial?)

Thought I could make out intuitively that as there is only one place where $$f_1[n]$$ and $$f_2[n]$$ are called, which is in $$f^\star$$, so probably in $$(4)$$ we get the required relation.

But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition.

[Note: However an alternative to mathematical induction shall be more helpful as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then even mathematical induction is appreciated if I can get the intuition behind the proof)].

It looks like that you are exhausted after a long and tiring journey that you have taken to comprehend the setup of assembly-line scheduling, the step 1 on the structure of the fastest way through the factory and the step 2 on a recursive solution.

It is straightforward to understand formula (4) and (5).

When we program a recursion solution using formula (1), (2) and (3), the left-hand side of each formula is transformed to the signature of its implementing method while the right-hand side is transformed to the body of the method.

For example, (3) is transformed to pseudo-Python code

def f_star(n):
return min(f_1(n) + x_1, f_2(n) + x_2)


So, when $$f^\star$$ is referenced, i.e., when f_star is called, $$f_1[n]$$ and $$f_2[n]$$ will be referenced, i.e., f_1(n) and f_2(n) will be called, where f_1(.) and f_2(.) will be explained below. Since we will call f_star(n) once, which is enough to get the value of $$f^\star$$, we get formula (4).

Formula (1) is transformed to pseudo-Python code

def f_1(j):
if j == 1:
return e + a
else:
return min(f_1(j - 1) + a[j], f_2(j - 1) + t[j - 1] + a[j])


So whenever $$f_1[j]$$ is referenced, i.e., when $$f_1(j)$$ is called, $$f_1[j-1]$$ will be referenced exactly one, i.e., f_1(j-1) will be called exactly once.

Similarly, whenever $$f_2[j]$$ is referenced, $$f_1[j-1]$$ will be referenced exactly once. (You can write the function f_2(j) explicitly yourself to check it out.)

Note that any reference to $$f_1[j-1]$$ must be brought by either a reference to $$f_1[j]$$ or a reference to $$f_2[j]$$. So we have $$r_1(j-1) = r_1(j) + r_2(j).$$

Similarly or by symmetry, we also have $$r_2(j-1) = r_1(j) + r_2(j).$$

Replacing $$j$$ by $$j+1$$, we get formula (5).

• thanks a lot for the help. – Abhishek Ghosh Jul 1 at 5:56
• Welcome. $\phantom{}$ – John L. Jul 1 at 6:34