由于“超过最大递归深度”，如何将递归函数转换为迭代函数？

Question

我试图将递归函数转换为基于python限制的迭代函数。你知道吗

我正在将在this answer中找到的算法从Javascript改编为Python。为了更好地解释算法，我建议阅读我链接的答案，因为它更简洁。高层次的目的是沿着由lat/lng对（点）组成的“线”找到等距点。但是，由于Python中最大递归深度的限制，我在递归move_along_path函数中遇到了一些问题。在阅读了一些类似的问题之后，我发现最好的办法是将它转换成一个迭代函数。我甚至开始转换都有困难。你知道吗

这是我改编的两个函数，其中move_along_path是递归函数（只有一个需要转换），有时也调用move_towards。你知道吗

如何开始转换？转换时需要考虑哪些基本步骤？你知道吗

# This is the base function that calls the recursive function
def get_equidistant_markers_from_polyline_points(self, points):
    points = points[1::10]
    # Get markers
    next_marker_at = 0
    markers = []
    while True:
        next_point = self.iterative_move_along_path(points, next_marker_at)

        if next_point is not None:
            markers.append({'lat': next_point[0], 'lng': next_point[1]})
            next_marker_at += 80000  # About 50 miles
        else:
            break
    print(markers)
    return markers

# This function moves from point to point along a "path" of points. 
# Once the "distance" threshold has been crossed then it adds the point
# to a list of equidistant markers.
def move_along_path(self, points, distance, index=0):
    if index < len(points) - 1:
        # There is still at least one point further from this point
        # Turn points into tuples for geopy format
        # point1_tuple = (points[index]['latitude'], points[index]['longitude'])
        # point2_tuple = (points[index + 1]['latitude'], points[index + 1]['longitude'])
        point1_tuple = (points[index]['lat'], points[index]['lng'])
        point2_tuple = (points[index + 1]['lat'], points[index + 1]['lng'])

        # Use geodesic method to get distance between points in meters
        distance_to_next_point = geopy.distance.geodesic(point1_tuple, point2_tuple).m

        if distance <= distance_to_next_point:
            # Distance_to_next_point is within this point and the next
            # Return the destination point with moveTowards()
            return self.move_towards(point1_tuple, point2_tuple, distance)

        else:
            # The destination is further from the next point
            # Subtract distance_to_next_point from distance and continue recursively
            return self.move_along_path(points, distance - distance_to_next_point, index + 1)

    else:
        # There are no further points, the distance exceeds the length of the full path.
        # Return None
        return None



def move_towards(point1, point2, distance):
    # Convert degrees to radians
    lat1 = math.radians(point1[0])
    lon1 = math.radians(point1[1])
    lat2 = math.radians(point2[0])
    d_lon = math.radians(point2[1] - point1[1])

    # Find the bearing from point1 to point2
    bearing = math.atan2(math.sin(d_lon) * math.cos(lat2),
                         math.cos(lat1) * math.sin(lat2) -
                         math.sin(lat1) * math.cos(lat2) *
                         math.cos(d_lon))

    # Earth's radius
    ang_dist = distance / 6371000.0

    # Calculate the destination point, given the source and bearing
    lat2 = math.asin(math.sin(lat1) * math.cos(ang_dist) +
                     math.cos(lat1) * math.sin(ang_dist) *
                     math.cos(bearing))
    lon2 = lon1 + math.atan2(math.sin(bearing) * math.sin(ang_dist) *
                             math.cos(lat1),
                             math.cos(ang_dist) - math.sin(lat1) *
                             math.sin(lat2))

    if math.isnan(lat2) or math.isnan(lon2):
        return None

    return [math.degrees(lat2), math.degrees(lon2)]

Answer 1

假设您发布的代码是正确的，我认为以下函数可以作为一种迭代方法来替换当前的递归函数：

def iterative_move_along_path(self, points, distance, index=0):
    while index < len(points) - 1:
        # There is still at least one point further from this point
        # Turn points into tuples for geopy format
        # point1_tuple = (points[index]['latitude'], points[index]['longitude'])
        # point2_tuple = (points[index + 1]['latitude'], points[index + 1]['longitude'])
        point1_tuple = (points[index]['lat'], points[index]['lng'])
        point2_tuple = (points[index + 1]['lat'], points[index + 1]['lng'])

        # Use geodesic method to get distance between points in meters
        distance_to_next_point = geopy.distance.geodesic(point1_tuple, point2_tuple).m

        if distance <= distance_to_next_point:
            # Distance_to_next_point is within this point and the next
            # Return the destination point with moveTowards()
            return self.move_towards(point1_tuple, point2_tuple, distance)

        else:
            # The destination is further from the next point
            # Subtract distance_to_next_point from distance and continue recursively
            distance -= distance_to_next_point
            index += 1

    # There are no further points, the distance exceeds the length of the full path.
    # Return None
    return None

当从递归返回时，由于递归的一个步骤似乎与先前计算的值没有依赖关系，因此应该简单而正确地插入while循环并适当地更新变量。你知道吗