Using recursion in Python class methods

Question

NB Noob alert ... !

I am trying to use recursion in a Python class method, but with limited results.

I'm trying to build a car class, with very basic attributes: id, position in a one lane road (represented by an integer), and velocity. One of the functions I have is used to return which car id is in front on this one -- i.e. if we have class:

class Car:
    def __init__(self, position, id, velocity):
        self.position = position
        self.id = id
        self.velocity = velocity

Now, I've come up with the following class method (additional details below the code):

def findSuccessorCar(self, cars):

    successorCar = ""
    smallestGapFound = 20000000 

    for car in cars:
        if car.id == self.id: continue

        currentGap = self.calculateGap(car)

        if (currentGap > -1) and (currentGap < smallestGapFound):
            smallestGapFound = currentGap
            successorCar = car

    if successorCar == "":
        return 1 # calling code checks for 1 as an error code
    else:        
        return successorCar

The plan is to create car objects, then store them in a list. Each time the findSuccessorMethod is called, this global list of cars is passed to it, e.g.

    c1 = testCar.Car(4, 5, 1) # position, pos_y, Vel, ID
        c2 = testCar.Car(7, 9, 2)
        c3 = testCar.Car(9, 1, 2)
        cars = [c1, c2, c3]

        c1_succ = c1.findSuccessorCar(cars)

This works fine: the find successor car function will say that car c2 is in front of car c1 (position 7 ahead of position 4).

However, I want car c1 to work out what car is in front of its immediate successor -- that is, which car is in front of the car in front, which in this case is car c3. My thinking was that if I did c1_succ.findSuccessorCars(cars) then this should work fine: doing type(c1_succ) shows it is an instance and hasattr shows that it has the anticipated object attributes.

However, when I do try to execute c1_succ.findSuccessorCars(cars), an integer is returned. Hence, I am confused -- why doesn't this work? Why can you not recursively execute a class method in this fashion? Where does this integer come from?

NB Gut feel says that this has something to do with the self declaration, and that I'll need to modify my code so that as well as a global list of cars, there'll need to be a global list of their current positions, or another class method, e.g. findSuccessorsSuccessor (yes, fully aware of crummy naming!). However, I am interested to understand why this recursive approach does not work.

UPDATE

Here is the requested code for calculating a gap between 2 cars -- I appreciate it is very basic, so not too much laughter at the back please.

    def calculateGap(self, car):
        ''' Calculate the gap between two cars
        '''
        thisCar = self
        otherCar = car

        gap = otherCar.position_x - thisCar.position_x 

        return gap

Can you post the code for calculateGap? Then it should be possible to reproduce what you're seeing. — mikej
– mikej, Commented Aug 12, 2010 at 9:11
@The MYYN, that's not a good idea; sys.maxint + 1 is a valid integer. None makes a better sentinel. — habnabit
– habnabit, Commented Aug 12, 2010 at 9:20

habnabit · Accepted Answer · 2010-08-12 09:18:47Z

5

What you're calling a class method is actually an instance method. Class methods operate on the class, and instance methods operate on the instance. Here, we're dealing with Car instances, not the Car class itself.

class Car(object):
    def __init__(self, position, id, velocity):
        self.position = position
        self.id = id
        self.velocity = velocity

    def __eq__(self, other):
        return self.id == other.id

    def __str__(self):
        return 'Car(%d, %d, %d)' % (self.position, self.id, self.velocity)

    def calculateGap(self, other):
        return other.position - self.position

    def findSuccessor(self, cars):
        ret = smallestGap = None
        for car in cars:
            if car == self:
                continue
            gap = self.calculateGap(car)
            if gap < 0:
                continue
            if smallestGap is None or gap < smallestGap:
                ret, smallestGap = car, gap
        return ret

    def findNthSuccessor(self, n, cars):
        cur = self
        for x in xrange(n):
            cur = cur.findSuccessor(cars)
            if cur is None:
                return None
        return cur

c1 = Car(4, 5, 1)
c2 = Car(7, 9, 2)
c3 = Car(9, 1, 2)
cars = [c1, c2, c3]

print c1.findSuccessor(cars)
print c1.findSuccessor(cars).findSuccessor(cars)
print c1.findNthSuccessor(2, cars)

Output:

Car(7, 9, 2)
Car(9, 1, 2)
Car(9, 1, 2)

answered Aug 12, 2010 at 9:18

habnabit

10.4k3 gold badges35 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Katriel Over a year ago

I still don't understand why you are implementing your own sort instead of using Python's!

Dan Weavesham Over a year ago

Thanks for providing the code example. However, I'm still struggling to understand: why does your version work and mine does not?

Katriel · Accepted Answer · 2010-08-12 09:34:26Z

2

Your method does work in theory; this is an implementation bug. That said, it is not the right way to do things; specifically, findSuccessorCar should not be a class method of Car. This is because the list of Car instances is a separate construct; the class Car doesn't and shouldn't know anything about it. If you wanted to make a class for it you should make a Road which is a list of Cars, and put findSuccessorCar on that.

That said, I don't see why you can't do

import operator
cars.sort( key = operator.attrgetter( "position" ) )

to sort the list of cars in position order. I think you're implementing your own sorting algorithm to find the successor car?

Other points of note: you should use exceptions (raise BadCarMojoError) to indicate failure, not magic return codes; classmethods traditionally use cls instead of self as the first argument; and Car should inherit from object.

import bisect

class Car( object) :
    def __init__( self, position, id, velocity ):
        self.position = position
        self.id = id
        self.velocity = velocity

    def __lt__( self, other ):
        return self.position < other.position

class Road( object ):
    def __init__( self ):
        self.cars = [ ]

    def driveOn( self, car ):
        bisect.insort( self.cars, car )

    def successor( self, car ):
        i = bisect.bisect_left( self.cars, car )
        if i == len( self.cars ):
            raise ValueError( 'No item found with key at or above: %r' % ( car, ) )
        return self.cars[ i + 1 ]

c1 = Car( 4, 5, 1 )
c2 = Car( 7, 9, 2 )
c3 = Car( 9, 1, 2 )
c1 < c2

road = Road( )

for car in ( c1, c2, c3 ):
    road.driveOn( car )

c1_succ = road.successor( c1 )

edited Aug 12, 2010 at 9:34

answered Aug 12, 2010 at 9:15

Katriel

124k19 gold badges141 silver badges172 bronze badges

2 Comments

S.Lott Over a year ago

+1: Separate Car from Road. Car.successor( self, road ) can be added so that the original "successor" works, given a specific Road object.

aaronasterling Over a year ago

I would have Car have a road instance attribute that is set by Road.driveOn so that you don't have to go through every instance of Road to find out which one a particular car is on.

Collectives™ on Stack Overflow

Using recursion in Python class methods

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related