# Recursive factorial algorithm

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