在Python类方法中使用递归

Question

注意：新手警报！

我正在尝试在一个Python类的方法中使用递归，但结果不太理想。

我想创建一个汽车类，里面有一些基本属性：汽车的ID、在单车道上的位置（用一个整数表示）和速度。我有一个函数是用来返回在这辆车前面的汽车ID，也就是说，如果我们有这样的类：

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

现在，我想出了以下的类方法（代码下面有更多细节）：

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

计划是创建汽车对象，然后把它们存储在一个列表里。每次调用findSuccessorMethod时，这个全球的汽车列表会被传递给它，比如：

    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)

这个方法运行得很好：find successor car函数会说汽车c2在汽车c1的前面（位置7在位置4的前面）。

但是，我希望汽车c1能够找出它的直接后继车前面是哪辆车，也就是说，找出在c1前面的车的前面是哪辆车，在这个例子中是汽车c3。我想，如果我执行c1_succ.findSuccessorCars(cars)，应该可以正常工作：用type(c1_succ)查看它是一个实例，用hasattr查看它有预期的对象属性。

然而，当我尝试执行c1_succ.findSuccessorCars(cars)时，返回的是一个整数。这让我感到困惑——为什么这样不行？为什么不能以这种方式递归执行类方法？这个整数是从哪里来的？

注意：我感觉这可能和self声明有关，我需要修改我的代码，不仅要有一个全球的汽车列表，还需要有一个它们当前位置信息的全球列表，或者另一个类方法，比如findSuccessorsSuccessor（是的，我知道这个名字很糟糕！）。不过，我想了解为什么这个递归的方法不奏效。

更新

这是计算两辆车之间间隙的代码——我知道这很基础，所以请不要在后面笑得太厉害。

    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

你的方法理论上是可行的，但这是一个实现上的错误。不过，这并不是正确的做法；具体来说，findSuccessorCar 不应该是 Car 类的方法。这是因为 Car 实例的列表是一个独立的结构；Car 类不应该也不需要知道这个列表的存在。如果你想为这个列表创建一个类，应该创建一个 Road 类，它是一个 Cars 的列表，然后把 findSuccessorCar 放在这个类里。

话虽如此，我不明白为什么你不能这样做

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

来按位置顺序对汽车列表进行排序。我觉得你是在实现自己的排序算法来找到下一个汽车吗？

还有几点需要注意：你应该使用异常（raise BadCarMojoError）来表示失败，而不是使用神秘的返回代码；类方法通常使用 cls 作为第一个参数，而不是 self；而且 Car 应该继承自 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 2

你所说的类方法其实是实例方法。类方法是作用于整个类的，而实例方法是作用于实例的。在这里，我们讨论的是汽车的实例，而不是汽车这个类本身。

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)

输出：

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