时间戳

首页 > 解决方案 > 由于“超出最大递归深度”，如何将递归函数转换为迭代？

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

问题描述

我正在尝试将递归函数转换为基于 python 限制的迭代函数。

我正在调整我在这个答案中找到的算法，从 Javascript 到 Python。为了更好地解释算法，我建议阅读我链接的答案，因为它更简洁。这样做的高级目的是沿着由 lat/lng 对（点）组成的“线”找到等距点。move_along_path但是，由于 Python 中的最大递归深度限制，我在递归函数中遇到了问题。在阅读了一些类似的问题后，我发现最好的办法是将其转换为迭代函数。我什至在开始转换时都遇到了麻烦。

这是我改编的两个函数，其中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)]

标签： pythonrecursion

解决方案

我不是最好的python，所以我相信你可以优化它，但一般的想法是，你可以做一个while循环，而不是调用递归函数，直到满足你的条件，然后在循环中修改变量如果你将它们作为参数发送给递归函数，你会做什么。

def move_along_path(self, points, distance, index=0):
    if index < len(points) - 1:
        point1_tuple = (points[index]['lat'], points[index]['lng'])
        point2_tuple = (points[index + 1]['lat'], points[index + 1]['lng'])
        distance_to_next_point = geopy.distance.geodesic(point1_tuple, point2_tuple).m

        while distance > distance_to_next_point:
            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
            distance -= distance_to_next_point
            index++


        return self.move_towards(point1_tuple, point2_tuple, distance)
    else
        return None

推荐阅读