How to use recursion in python

Question

I am trying to solve a problem which stimulate movements of a robot. The robot starts with position (0, 0, 'N'). The command is given in a list of strings. the 'turn' function turns from N to E to S to W and back to N. The move function moves in the specific direction: N,S in y axis and E,W in x axis. N: y+1 S: y-1 W: x-1 E: x+1

The part I am having trouble with is, when trying to use shortcuts in the function. Using 'turnleft' instead of ['turn', 'turn', 'turn'], 'turnright' instead of 'turn'

def macro_interpreter(code, macros):

when call the function:

print(macro_interpreter(['turnleft', 'turnright'], {'turnleft': ['turn', 'turn', 'turn'], 'turnright' : ['turn'], 'bigleftturn' : ['move', 'move', 'turnleft', 'move', 'move'], 'bigrightturn' : ['move', 'move', 'turnright', 'move', 'move']}))

the definition of the term is given in a dictionary. My code only runs for the first command and then terminate, it ignores the second code in the list

def macro_interpreter(code, macros):
    x,y,index = 0, 0, 0
    state = ['N', 'E', 'S', 'W']
    for command in code:
        if command in macros:
            return macro_interpreter(macros[command], macros)
        else:
            if command == 'move':
                if state[index] == 'N':
                    y += 1
                elif state[index] == 'E':
                    x += 1
                elif state[index] == 'S':
                    y -= 1
                elif state[index] == 'W':
                    x -= 1
            elif command == 'turn':
                try:
                    index = index + 1
                except IndexError:
                    index = 0
    return (x, y, state[index])

what's your expected output?. as far as i can see turn isn't present in your macro's (on the second run) and 'move' wasn't part of the codes returned also, so the other conditions under that block will never run....and also incrementing a number would never raise an IndexError, rather trying to access a list with a missing index would. — danidee
– danidee, Commented Oct 15, 2016 at 12:50

OneCricketeer · Accepted Answer · 2016-10-15 13:13:28Z

If you always hit the one else statement in the loop over the code commands, then you never will recurse because command not in macros.

After the first iteration, code == ['turn', 'turn', 'turn'], but macros contains no key "turn"

If you wish to do this more correctly, then you can pass along x, y, and the "direction index state" as parameters to the function, then increment / modify those within the recursive call rather than only modify local variables of the function and always restart them back at (0,0, 0).

Also, you need to replace that try except with index = (index + 1) % len(state) because no IndexError is going to be caught by incrementing a number

So, something like this

state = ['N', 'E', 'S', 'W']
def macro_interpreter(code, macros, x=0,y=0,index=0):
    # TODO: check if x or y have gone outside "the board" 
        # TODO: return to break from recursion 

    for command in code:
        if command in macros:
            return macro_interpreter(macros[command], macros,x,y,index)
        else:
            if command == 'move':
                if state[index] == 'N':
                    return macro_interpreter(code[1:], macros,x,y=y+1,index)

Akshay Pratap Singh · Accepted Answer · 2016-10-15 13:17:44Z

There are some amendments which i did in your code to support recursion properly. This code will do, what you want to acheive.

def macro_interpreter(code, macros, x=0, y=0, index=0):
    state = ['N', 'E', 'S', 'W']
    for command in code:
        if command in macros:
            x, y, curr_state = macro_interpreter(macros[command], macros, x, y, index)   
            # update new index with new state value         
            index = state.index(curr_state)
        else:
            if command == 'move':
                if state[index] == 'N':
                    y += 1
                elif state[index] == 'E':
                    x += 1
                elif state[index] == 'S':
                    y -= 1
                elif state[index] == 'W':
                    x -= 1
            elif command == 'turn':                
                index = (index + 1)%len(state)
    return (x, y, state[index])

Now, if i run your test case

>> print macro_interpreter(['turnleft', 'turnright'], {'turnleft': ['turn', 'turn', 'turn'], 'turnright' : ['turn'], 'bigleftturn' : ['move', 'move', 'turnleft', 'move', 'move'], 'bigrightturn' : ['move', 'move', 'turnright', 'move', 'move']})
 Output:- (0, 0, 'N')

I hope this will helps you.

Jacques de Hooge · Accepted Answer · 2016-10-15 12:47:52Z

0

The line

return macro_interpreter (macros etc.

will do just that. It will leave the for loop and return from the outer call. End of story.

answered Oct 15, 2016 at 12:47

Jacques de Hooge

7,0102 gold badges33 silver badges49 bronze badges

Comments

Thomas Kilkelly · Accepted Answer · 2016-10-15 13:01:16Z

0

I suspect it's because you return

macro_interpreter(macros[command], macros)

This simply exits the function once the recursed code is run. You'll see if you change

return macro_interpreter(macros[command], macros)

to

print macro_interpreter(macros[command], macros)

that the code will print what you want it to do. How you want to actually handle the output is up to you.

answered Oct 15, 2016 at 13:01

Thomas Kilkelly

12510 bronze badges

Collectives™ on Stack Overflow

How to use recursion in python

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related