How to convert recursive function to iterative due to 'max recursion depth exceeded'?

Question

I'm trying to convert a recursive function to an iterative one based on python limitations.

I am adapting an algorithm that I found in this answer from Javascript to Python. For a better explanation of the algorithm I'd suggest reading the answer I linked because it's much more concise. The high level purpose of this is to find equidistant points along a "line" made up of lat/lng pairs (points). However I'm running into issues in the recursive move_along_path function due to maximum recursion depth limitations in Python. After reading some similar questions, I found the best thing to do is to convert it to an iterative function. I am having trouble even beginning the conversion.

These are the two functions I have adapted, where move_along_path is the recursive function (only one that needs converting) that sometimes calls move_towards as well.

How can I begin this conversion and what are some basic steps to consider when converting?

# 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)]

Welcome to Stack Overflow! Could you add to your question a high-level explanation about the purpose of each function in your code? — Hemerson Tacon, Jan 29 '19 at 20:50
Possible duplicate of [Way to go from recursion to iteration](https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) — hnefatl, Jan 29 '19 at 20:53
@HemersonTacon I edited it to be a little clearer, let me know if that helps. Thanks! — RyTom, Jan 29 '19 at 21:04
Hi RyTom, please make sure that your code example is Minimal, Complete, and Verifiable. Right now it's missing the import statements, and these methods are obviously part of some class. It'd also be nice if you could post the output of your code and what you expect the output should be if it were working correctly. https://stackoverflow.com/help/mcve — Al Sweigart, Jan 30 '19 at 04:30
@AlSweigart Thanks! Still new to this, so I should post the whole class, but it needs to be minimal? Not sure how to fit both those requirements. — RyTom, Jan 30 '19 at 04:51

score 0 · Answer 1 · answered Jan 29 '19 at 21:03

I'm not the best with python so I'm sure you can optimize this but the general idea is that instead of calling a recursive function you can just do a while loop until your condition is met and in the loop you modify the variables in accordance to what you would've done had you sent them through as parameters to the recursive function.

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

There no such thing like `index++` in python – Hemerson Tacon Jan 29 '19 at 21:06 — Hemerson Tacon, Jan 29 '19 at 21:06

Hemerson Tacon · Accepted Answer · 2019-01-29T21:29:28.153

Assuming that your posted code are right, I think the following function works as an iterative approach to replace your current recursive function:

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

As a step of your recursion doesn't seem to have a dependency relative to previously calculated values when returning from the recursion, a simple and right insertion of a while loop together with a proper update of the variables should work out.

Hey thank you so much. It's almost perfect except in the `else` statement index should be incremented by one: `index += 1`. Took a few minutes to figure it out but I can't complain too much, you just helped me out a ton, thanks!! — RyTom, Jan 29 '19 at 21:24
Whops, my bad. I wrote it fast and didn't revised, I will correct the post. — Hemerson Tacon, Jan 29 '19 at 21:29

How to convert recursive function to iterative due to 'max recursion depth exceeded'?

2 Answers2