Solving Recurrence Relations (Nonlinear?)

Question

I'm not sure the term, but how do you solve a recurrence relation with a multiplicative factor in the index, so as opposed to $a_n=a_{n-1}+a_{n-2}$ we have something like $a_n=a_{\frac{n}{2}}$. I know that it's easy to guess solutions often, but is there a methodological way of doing this, like characteristic polynomials?