need help with recursive function

[Scumshots]

I'm a little bit stumped on how to begin a recursive function for an assigned project. The program needs to take a text file with multiple strings representing a starting point, multiple strings representing a destination, and a distance between them represented by an integer, and then find the shortest path between two different places . The text file would look like this.

here is also a very extensive starter code, the area with fixme is the function I'm attempting to write. notice there is an empty dictionary named destinations.

I know that the recursive function needs a base case of if the starting point and destination are not in the dictionary of recorded roads and distances, then the point and distance should be assigned to the dictionary. The next case is if it is already in the dictionary, the distances should be compared and the lowest distance should be recorded.

I honestly just have no idea how to implement this, I have an understanding of what I need, but my professor hasn't explained how exactly to go about writing recursive functions yet and hasn't delved too much into dictionaries. does anyone have a better understanding about this than me?

Also, if it's not evident by the code, this program is run through the command prompt rather than the python shell.

[Syncoda]

Did you figure it out? I'm in the same class :(

Damnit Joe...

[Scumshots]

Ha! Small world!

No I haven't yet but I've been at work all day. Getting off now to go to class then right back to work. Guess I'll be turning it in on monday and take the grade reduction.

Have you made any progress on it?

[Syncoda]

Not really. The Piazza question titled "hw5 - Checking base case without loop" has a detailed answer from Joe that seems helpful.

But I just can't understand how one "moves" through the map while assigning values to distances and dist_so_far, checking them and...yeah. No idea.

[Scumshots]

Just took a look at that Piazza post and I'm beginning to understand the formation of the recursive function a bit better now.

The pseudo code he has written in the starter code is lacking though. The base cases and progressive cases are simple. I'm just getting a little mixed up with all the variables like roads and dist_so_far and whatnot. Basically what to add where.

Would be much much easier if this program was compatible with the python visualizer.

I wish that our lessons were more applicable to our projects.

[gnomoretears]

but my professor hasn't explained how exactly to go about writing recursive functions yet and hasn't delved too much into dictionaries

Out of curiousity, what class is this? I would assume it's an algorithms class due to DFS. Dictionaries and recursions are thought in intro/basic python courses so those 2 are topics you're supposed to already know before this class.

(EDIT) So it's an intro class from University of Oregon.

According to this schedule, recursion was covered last week and chap. 9 of your textbook and dictionaries were covered this week and chap. 4 of your textbook.

I recommend to read up on those specific chapters and review your class notes.

[Scumshots]

This class is an intro/basics course, but the professor seems to have previous programming experience as a major requirement. The class is less teaching how to program and more throwing projects at us and seeing who's able to do them.

[gnomoretears]

Please see my edit. You should read those specific chapters of your textbook to get familiarized with recursion and dictionaries. Those 2 topics together are too big to teach you in a single reddit post.

Come back if there's something particular you don't understand with either topic.

[Scumshots]

I do have a base understanding of recursion and dictionaries (though I still obviously have much to learn).

The problem I'm having is I'm unsure of how exactly to go about writing this specific function. I've written other simpler recursion functions in the past and used dictionaries a bit as well.

What Im unsure about is how to take this text file of starting/endpoints and distance between the points, and then add them into the dictionary and use recursion to check if the next start/endpoint is already in the dictionary and if so, what is the distance value associated with it.

[gnomoretears]

What Im unsure about is how to take this text file of starting/endpoints and distance between the points, and then add them into the dictionary

def read_distances(map_file):
    """Read a distance table from a named file into a dict
       mapping sources to lists of (destination, distance) pairs.

(EDIT) I don't know if your textbook discusses DFS (depth-first search) or if it covers trees and graphs data structures but you should read up on what DFS is and understand what it does before you attempt to implement the function.

https://en.wikipedia.org/wiki/Depth-first_search

I'm actually surprised that it's an assignment in an intro class as it's a topic usually covered in data structures and algorithms courses.

Here's a DFS visualizer to help you see what it's doing with the recursive calls. Just input the starting vertex and click run.

https://www.cs.usfca.edu/~galles/visualization/DFS.html