Algorithm Factorial with two Arguments Function(n,m)

Question

I am solving my Homework and unable to understand the problem please explain me the question so that i can solve for the solution. The question is.

• Write a recursive function to compute the factorial using divide and conquer as in Merge-Sort. That is, assuming n m, write a function Factorial(n,m) that computes n(n − 1)(n − 2) · · · (m + 1)m. The top-level call will be Factorial(n, 1).

Help me in Understanding the problem with following things:-

1. Why there are two arguments in factorial function?
2. How will the execute like i understand that for the given problem if i choose n=8, m=5 the execution will be like 8x7x6x5 only? Is that correct?
3. As far as i have read for the methods of solving the factorial. Iterative and Recursion. They only take an input of 1 number i.e. Factorial(n) to compute for the value of n. ? Explain me how to start.

**

Answer 1

Like merge sort:

function EvalFact(x, y) {
    return x * y;
}

function Factorial(m, n) {
    z = m;
    If (m != n) {
        p = floor((n - m) / 2); //(integer division)
        x = Factorial(m, m + p);
        y = Factorial(m + p + 1, n);
        z = EvalFact(x, y);
    } 
    return z;
}

Call Factorial(1,n)

Answer 2

The answer is simple, Factorial(n,m) should not be visible to user...

In general, for writing some recursive logic, you need to pass some additional state to later method calls... but you can always hide this method from users view, and call from Factorial method with one parameter

Answer 3

The keyword is "divide and conquer". So that you can compute 20! by dividing the task into the products from 1 to 10 and secondly from 11 to 20, and then the product from 11 to 20 into products 11..15 and 16..20. etc.

Why you would do that is not that clear since the number of multiplications does not change. You may be able to balance bit lengths of factors in "big integer" scenarios.

Answer 4

if i get it right... written in javaScript this recursive function could be something like this...
version 1 (top level call is Factorial(n,1) ):

function Factorial(n,m) {
  if (m>1) {
    return Factorial(n, 1) / Factorial(m-1, 1);
  } else {
    if (n>1) {
      return n * Factorial(n-1, 1);
    } else {
      return 1;
    }
  }
}

but this - simpler version 2 will also work:

function Factorial(n,m) {
  if (n>m) {
    return n * Factorial(n-1, m);
  } else {
    return m;
  }
}

version 3 divide and conquer:

function factorial(n, m) {
  if (n == m) {
    return n;
  } else {
    if (m > n) {
      return 1;
    } else {
      return factorial(n, Math.round((n+m)/2) ) * factorial( Math.round((n+m)/2)-1 , m);
    }
  }
}