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).
