I'm struggling to understand this factorial algorithm.

Falling(n, m):
    if m = 0
        return 1
    if m = 1
        return n
    return Falling(n, floor(m/2))*
           Falling(n - floor(m/2), ceil(m/2))

The algorithm should compute $n!/(n-m)!$

I'm analyzing it in the case of n = m, i.e it returns n! Now I'm getting the correct results from my implementation of it in Java, but the correctness of it has shaking my head.

How should I approach this?


If you plug in the result in what is returned by the recursion, you get: $$\frac{n!}{(n - \lfloor \frac{m}{2} \rfloor)!} \frac{(n - \lfloor \frac{m}{2} \rfloor)!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!} = \frac{n!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!}$$

You can see the right side is equal to $\frac{n!}{(n - m)!}$ because of the identity $m = \lfloor \frac{m}{2} \rfloor + \lceil \frac{m}{2} \rceil$ (if you are in doubt about this: check the cases $m$ even and $m$ odd separately).

For correctness, the only thing left to check then is the base cases $m=0$ and $m=1$ are correct (which is a trivial observation), that Falling is not invoked with incorrect parameters (this is the case if $m \le n$ holds) and that it terminates (also the case because the invoked instances have strictly smaller parameters).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.