Reccurence algorithm: find position after n moves

There is a trivial solution to this: at stage 6, 7 and 8, the positions happen to be 0, 1 and -1 respectively, which are the same positions as the initial positions. As the next stage and position only depend on the previous pair of stages, and previous position, the same sequence is guaranteed to repeat.

And so the function to calculate the position for a given n, can just be:

def position(n):
    return [0, 1, -1, -4, -5, -3][n % 6]

And the function to calculate the stage with number n:

def stage(n):
    return [3, 1, -2, -3, -1, 2][n % 6]

For such kind of problems you must try finding solutions for some cases, may be you will find a pattern like I find which will help you to solve this problem in O(1) time and just a list of 6 elements.

Let's iterate it for few initial stages,

           Steps to take      New position
Stage 0        ---                0
Stage 1         1                 1
Stage 2        -2                -1
Stage 3        -3                -4
Stage 4        -1                -5
Stage 5         2                -3
Stage 6         3                 0
Stage 7         1                 1
Stage 8        -2                -1
Stage 9        -3                -4
Stage 10       -1                -5

So you can see that after Stage 6 the pattern repeats. So the following python code will help you solve this faster.

def getpos(n):
    '''Returns the position of the performer after nth stage.'''
    ls = [0, 1, -1, -4, -5, -3]
    return ls[n % 6]

def getstep(n):
    '''Returns the step taken at nth stage'''
    ls = [3, 1, -2, -3, -1, 2]
    if n == 0:
        return None
    return ls[n % 6]

The functions getpos() and getstep() are utility functions which you will need in this problem.

Okay; let's start with the recurrence definition:

stage(n) = stage(n-1) - stage(n-2)
pos(n) = pos(n-1) + stage(n)

Now, let's make our three variables:

pos is for pos(n)     -- position
ult is for stage(n-1) -- ultimate
pen is for stage(n-2) -- penultimate

The update is simple, given above. This initial values are given in the problem and your code:

pos = -1
ult = -2
pen = 1

Now, each time through the loop, update the values as given above.

stage_n = ult - pen
pos += stage_n

The last step is to prepare for the next iteration. When we take one more step, that becomes the ultimate for the next iteration; the current ultimate gets demoted to penultimate:

pen = ult
ult = stage_n

... and now we're ready to go back to the top of the loop.

Overall, it looks like this:

limit = <wherever you want to stop>

pos = -1
ult = -2
pen = 1

for n in range (3, limit):
    stage_n = ult - pen
    pos += stage_n

    pen = ult
    ult = stage_n

print "Step", limit, "is at position", pos