Which problem does the algorithm Delta below solve, where m, n >= 0 are integers?

So Im finding the algorithm very hard break down due to the nature of the nested recursion and how it calls on another recursive algorithm. If I had to guess I would say that Delta solves the LCS(longest common subsequence) problem, but Im not able to give a good explanation as to why.

Could someone help me break down the algorithm and explain the recursion and how it works?

CodePudding user response：

As you found out yourself, delta computes the product of two integers.

The recursion indeed makes this confusing to look at but the best way to gain intuition is to perform the computation by hand on some example data. But by looking at the functions separately, you will find that:

Gamma is just summation. Gamma(n,m) = gamma(n, m - 1) 1 essentially performs a naive summation where you count down the second term, while adding 1 to the first. Example:

3 3 =

(3 2) 1 =

((3 1) 1) 1 =

(((3 0) 1) 1) 1 =

6

Knowing this, we can simplify Delta:

Delta(n, m) = n Delta(n, m - 1) (if m!=0, else return 0).

In the same way, we are counting down on the second factor, but instead of adding 1, we add n. This is in indeed one definition of multiplication. It is easy to understand this if you manually solve an example just like above.