Using recursion in Python class methods

Question

Hello all,

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

Answer 1

If you wonder why an integer returned ...

if successorCar == "":
    return 1

A general answer: Try insert print or even better logging statements in your code, if your unsure, what happens when with which variables.

Answer 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 )

Answer 3

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)