Not sure if there is a general way to handle such recurrences but for the current case, this should help: https://en.wikipedia.org/wiki/Collatz_conjecture

You can make both transitions at the same time. Consider n even, using your example we have f(n) = f( 3*f(n-2)+1 )/2. As n will always be even just need to apply this n/2 times. If n is odd just do one transition by hand and use the same method.

So use a new function, change the exponent properly and handle some corner cases.

hx0 has written a Python decorator (description in Russian and English) which does exactly that. You can either read his description or my example here (or, actually, both):

General way:

First, write a program which solves the problem under the following limitations:

• You're not allowed to use functions.
• You're allowed to use a fixed number of variables only. No arrays, no dynamic memory.
• You're allowed to use a single loop only, which goes for a specific number of iterations, which can be easily calculated from n.
• You're only allowed to add variables together and multiply them by constants. You are not even allowed to add constants (although you're free to add an extra variable to hold value "one").

For example, here is the one for Fibonacci numbers:

prev2 = 0
prev1 = 0
for _ in range(n):
  prev2, prev1 = prev1, prev2 + prev1

And here is another for sum of squares (1² + 2² + 3² = 1 + 4 + 9 = 14). I'll go with this example from now on:

i = 1  # Current number
i2 = 1  # Its square, as we are prohibited from writing i*i
sum2 = 0  # Sum of squares of numbers [1..i)
one = 1  # Constant
for _ in range(n):
  sum2 += i2
  i2 += 2 * i + one  # (i+1)^2 = i^2 + 2 * i + 1
  i = i + one

Now, wonderful fact: the transformation you perform to that fixed set of variables on each iteration is actually a linear transformation which can be represented using matrix. You can see it that way: value of each variable after the iteration is some linear combination of values of variables before the iteration. In order to add constants, let's introduce For example, in the latter example we have the following transformation going on during a single iteration:

i_new = i_old + 1               = 1 * i_old + 0 * i2_old + 0 * sum2_old + 1 * one_old
i2_new = i2_old + 2 * i_old + 1 = 2 * i_old + 1 * i2_old + 0 * sum2_old + 1 * one_old
sum2_new = sum2_old + i2_old    = 0 * i_old + 1 * i2_old + 1 * sum2_old + 0 * one_old
one_new = one_old               = 0 * i_old + 0 * i2_old + 0 * sum2_old + 1 * one_old

Note that order of equivalences is the same as order of variables in each row — it's important, because now we're going to rewrite that transformation as a matrix:

 i i2  sum2 one
(1  1   0   1) * /1 2 0 0\ = (2 4 1 1)
                 |0 1 1 0|
                 |0 0 1 0|
                 \1 1 0 1/
(2  4   1   1) * /1 2 0 0\ = (3 9 5 1)
                 |0 1 1 0|
                 |0 0 1 0|
                 \1 1 0 1/
(3  9   5   1) * /1 2 0 0\ = (4 16 14 1)
                 |0 1 1 0|
                 |0 0 1 0|
                 \1 1 0 1/

Or, shortly:

 i i2  sum2 1
(1  1   0   1) * cubed /1 2 0 0\ = (4 16 14 1)
                       |0 1 1 0|
                       |0 0 1 0|
                       \1 1 0 1/

So, we've just transformed a simple loop iteration into a matrix. So, loop became matrix exponentiation and we can apply fast exponentiation trick.

http://fusharblog.com/solving-linear-recurrence-for-programming-contest-part-2/

I have a few doubts:
1. Does anyone know any question that uses the odd-even recurrence trick, as mentioned in the blog?
2. Is the Running time same as O(k³lg(n))?
3. Also is it possible to generalise this idea for solving a piecewise defined recurrence?