All but the very simplest recursions require heavy machinery to find closed forms. If you can't apply the Master Theorem often your best bet is to guess the answer and try an induction, otherwise you quickly end up with generating functions and differential equations.
