Permutation of phone numbers starting at button x, ending at button y, and z numbers long I am trying find the total number of permutations possible with a given x, y, and z. 
x is the initial number, y is the final number, and z is the total number of buttons pressed.
I am supposed to only move from number to number like the knight in chess, in an 'L' shape.
For example, if you just dialed a 1, the next number you dial has to be either a 6 or an 8. If you just dialed a 6, the next number must be a 1 or 7. 
Currently, my implementation outputs the correct answer for all the numbers I have given it. However, it is god awful slow because compute time is exponential. What I want to know is how I can compute this in linear time, more or less. z will always be between 1 and 100, inclusive.

##Computes the number of phone numbers one
##can dial that start with the digit x, end
##in the digit y, and consist of z digits in
##total. Output this number as a
##string representing the number in base-10.
##Must follow "knights rule" moves, like chess
##########_________##########
##########|1||2||3|##########
##########|_||_||_|##########
##########|4||5||6|##########
##########|_||_||_|##########
##########|7||8||9|##########
##########|_||_||_|##########
##########|_||0||_|##########
##########^^^^^^^^^##########
dict = {0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
    4: [0, 3, 9], 5: [], 6: [0, 1, 7], 7: [2, 6], 8: [1, 3],
    9: [2, 4]}


def recAnswer(current, y, z, count, total):
    if count == z and current == y:
            total += 1
            return total
    count+=1
    if count &gt; z:
            return total
    for i in dict.get(current):
            total = recAnswer(i, y, z, count, total)
    return total

def answer(x, y, z):
    if x == y:
            if z%2 == 0:
                    return '0'
    elif x == 5 or y == 5:
            if z == 1 and x == y:
                    return '1'
            else:
                    return '0'
    elif x%2 != 0 and y%2 == 0:
            if z%2 != 0:
                    return '0'
    elif x%2 == 0 and y%2 != 0:
            if z%2 != 0:
                    return '0'
    elif x%2 == 0 and y%2 ==0:
            if z%2 == 0:
                    return '0'
    elif x%2 != 0 and y%2 != 0:
            if z%2 == 0:
                    return '0'

    total = recAnswer(x,y,z,1,0)
    return str(total)

def test():
    for i in xrange(1,15,1):
            print i,":",answer(1,3,i)

    print answer(6, 2, 5)
    print answer(1, 6, 3)
    print answer(1, 1, 99)


test()
One probable solution could be to modify the code as this:


Have the code inside answer in another function, say, isNotTraversalCandidate which returns 0,1 if it the conditions confirm that no further traversal is required else it returns -1.
In recAnswer() use this function, isNotTraversalCandidate(), for the input x, y, z in every level. The recursive function should also verify the x, y, z with those conditions.