It took me some time to fully understand this recursive approach, but I think this is a great solution! Here is a very detailed explanation if anyone is wondering:

Denote L as traversing [1,...,n] from left to right, R as traversing [1,...,n] from right to left.

When n is odd:

L(1234567) = R(246) = R(123)*2

R(1234567) = L(246) = L(123)*2

When n is even:

L(123456) = R(246) = R(123)*2

R(123456) = L(135) = L(123) + 1 (a bit tricky)