What's the best way to structure a recursive long running algorithm?

I have built recursive path finding algorithm, it seems fairly quick but it also blocks the main update loop while it's running. I was thinking to move it to a set of recursively called co-routines or another thread but I'm unsure which would be best - I'd like to be able to call it fairly regularly without worrying about the impact on the game.

The current structure of my code is basically the following, with the path-finding code removed (as it's not really the point of my question), just outlining the amount of recursion it has - so I was considering if I should split the method calls to co-routines?

 void Update() {
 ....
 DefineRoutes(this.transform.position, Target);
 ....
 }
 
 void DefineRoutes(Vector3 CurrentPosition, GameObject TargetObject)
 {
 ......
 PlotRoute(this.transform.position, Target, 0);
 ......
 }
 
 void PlotRoute(Vector3 CurrentPosition, GameObject TargetObject, int RouteNumber)
 {
 .....
 NextPoint(CurrentPosition, TargetObject);
 .....
 }
 
 RoutePoint NextPoint (Vector3 StartingPoint, GameObject TargetObject)
 {
 ......
 TestRoutePoint(StartingPoint, rotated, TargetObject);
 ......
 }
 
 PossibleRoutePoints TestRoutePoint(Vector3 StartingPoint, Vector3 heading, GameObject TargetObject)
 {
 ......
 return;
 ......
 }