Recursion doesnt run as expected Algorithm For City solving problem

Question

This is my code for recursion, for solving a cities problem. Each city has at most 1 train and 1 bus station and some cities have both bus and train station.

So I run my code, it works but Recursion doesnt run I expect.

So far example if current station is "bus" and there is a train station in that city, hence, take the first if condition

if currentStation == "Bus" and currentCity in CitiesWithTrain: #check if trainStationExists

This runs but the next one with only "bus" condition, doesnt run anything inside. The if i am referring to is

if currentStation == "Bus"

and I dont return anything before that, just run a recursive call. Why doesnt the next if conditions get triggered ?

So the recursion doesnt keep going. Why doesn't the function run that ? so My output is below, keeps appending to the array but this is supposed to be happening with many running threads, not only one that keeps going (not like depth first search) I want to do it recursive.

from copy import copy
import sys
sys.setrecursionlimit(10000)

visitedCities = []
Cities = {"Istanbul" : 0, "Bursa" : 0, "Eskisehir" : 0, "Agri" : 0, "Temel" : 0, "SomeCity": 0, "Venzan": 0, "Milan": 0}

totalCostsSaved = {
    "Istanbul" : copy(Cities), 
    "Bursa" : copy(Cities), 
    "Eskisehir" : copy(Cities),
    "Agri" : copy(Cities), 
    "Temel" : copy(Cities), 
    "SomeCity": copy(Cities), 
    "Venzan": copy(Cities), 
    "Milan": copy(Cities)
}

#To find Quickest Itenaries from city, just set these variables Istanbul-Bus instead of istanbul-harem for example
startCity = "Temel" #City C 
startStation = "Bus" #Station of City


StationAverageTimeChange = { "Istanbul" : 30, "Eskisehir" : 10, "Temel": 50}

Bus = { "Istanbul-Bursa" : 100, "Bursa-Eskisehir" : 120, "Istanbul-Temel": 400 }
Train = { "Istanbul-Eskisehir" : 180, "Milan-Istanbul" : 80, "Venzan-Istanbul": 230, "SomeCity-Venzan" : 350, "Temel-Eskisehir": 290}

CitiesWithTrain = ["Istanbul", "Eskisehir", "Milan", "Venzan", "SomeCity", "Temel"]
CitiesWithBus = ["Istanbul", "Bursa", "Eskisehir", "Temel"]



def getCostToDestination(currentCity, currentStation, currentCost, TraveledPathsBus, TraveledPathsTrain):

    print(currentCity, currentStation, currentCost, TraveledPathsBus, TraveledPathsTrain)

    for city in totalCostsSaved.keys():
        if currentCity == city:
          continue
        
        if currentStation == "Bus" and currentCity in CitiesWithTrain: #check if trainStationExists
          for cityPairs in Train.keys():
            if currentCity in cityPairs.split("-"):
              for cit in cityPairs.split("-"):
                if cit != currentCity:
                  costToNewCity = currentCost + Train[cityPairs] + StationAverageTimeChange[currentCity]
                  if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                    totalCostsSaved[currentCity][cit] = costToNewCity
                  if cityPairs not in TraveledPathsTrain:
                    TraveledPathsTrain.append(cityPairs)
                    getCostToDestination(cit, "Train", currentCost + costToNewCity, TraveledPathsBus, TraveledPathsTrain)
        if currentStation == "Bus":
          for cityPairs in Bus.keys():
            if currentCity in cityPairs.split("-"):
              for cit in cityPairs.split("-"):
                if cit != currentCity:
                  costToNewCity = currentCost + Bus[cityPairs]
                  if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                    totalCostsSaved[currentCity][cit] = costToNewCity
                  if cityPairs not in TraveledPathsBus:
                    TraveledPathsBus.append(cityPairs)
                    getCostToDestination(cit, "Bus", currentCost + costToNewCity, TraveledPathsBus, TraveledPathsTrain)



        if currentStation == "Train" and currentCity in CitiesWithBus: #check if bus
          for cityPairs in Bus.keys():
              if currentCity in cityPairs.split("-"): 
                for cit in cityPairs.split("-"):
                  if cit != currentCity:
                    costToNewCity = currentCost + Bus[cityPairs] + StationAverageTimeChange[currentCity]
                    if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                      totalCostsSaved[currentCity][cit] = costToNewCity
                    if cityPairs not in TraveledPathsBus:
                        TraveledPathsBus.append(cityPairs)
                        getCostToDestination(cit, "Bus", currentCost + costToNewCity, TraveledPathsBus, TraveledPathsTrain)
        if currentStation == "Train":
          for cityPairs in Train.keys():
              if currentCity in cityPairs.split("-"):
                for cit in cityPairs.split("-"):
                  if cit != currentCity:
                    costToNewCity = currentCost + Train[cityPairs]
                    if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                      totalCostsSaved[currentCity][cit] = costToNewCity
                    if cityPairs not in TraveledPathsTrain:
                        TraveledPathsTrain.append(cityPairs)
                        getCostToDestination(cit, "Train", currentCost + costToNewCity, TraveledPathsBus, TraveledPathsTrain)
        


getCostToDestination(startCity, startStation, 0, [], [])


print(totalCostsSaved[startCity])

here is the output

Temel Bus 0 [] []
Eskisehir Train 340 [] ['Temel-Eskisehir']
Bursa Bus 810 ['Bursa-Eskisehir'] ['Temel-Eskisehir']
Istanbul Bus 1720 ['Bursa-Eskisehir', 'Istanbul-Bursa'] ['Temel-Eskisehir']
Eskisehir Train 3650 ['Bursa-Eskisehir', 'Istanbul-Bursa'] ['Temel-Eskisehir', 'Istanbul-Eskisehir']
Milan Train 3550 ['Bursa-Eskisehir', 'Istanbul-Bursa'] ['Temel-Eskisehir', 'Istanbul-Eskisehir', 'Milan-Istanbul']
Venzan Train 3700 ['Bursa-Eskisehir', 'Istanbul-Bursa'] ['Temel-Eskisehir', 'Istanbul-Eskisehir', 'Milan-Istanbul', 'Venzan-Istanbul']
SomeCity Train 7750 ['Bursa-Eskisehir', 'Istanbul-Bursa'] ['Temel-Eskisehir', 'Istanbul-Eskisehir', 'Milan-Istanbul', 'Venzan-Istanbul', 'SomeCity-Venzan']
Temel Bus 3840 ['Bursa-Eskisehir', 'Istanbul-Bursa', 'Istanbul-Temel'] ['Temel-Eskisehir', 'Istanbul-Eskisehir', 'Milan-Istanbul', 'Venzan-Istanbul', 'SomeCity-Venzan']
{'Istanbul': 400, 'Bursa': 470, 'Eskisehir': 340, 'Agri': 0, 'Temel': 630, 'SomeCity': 4050, 'Venzan': 1980, 'Milan': 1830}

where it is supposed to be

Temel Bus 0 [] []
Eskisehir Train 340 [] ['Temel-Eskisehir']
Istanbul Bus 400 ['Istanbul-Temel'][]

Etc. etc. and keep it recursive

So there are 4 if conditions if one Meets the condition, the rest doesnt run even if they were true. And I dont return anything

The tags `recursion` and `dijkstra` seem mutual exclusive to me. Dijkstra's algorithm is for finding shortest paths (which I think you want to do), but this doesn't use a stack, but a priority queue. So which of the two are you looking for? Recursion (like depth first) is not really that handy for finding shortest paths... Could you also state more explicitly what the *goal* is of the algorithm? Is it to find the shortest paths by any means, also potentially a mix of transport methods (bus for first half of trip, train for second half)? Can you also explain the output format? — trincot, May 23 '22 at 08:45
so right now i am just trying to run that 2nd recursive call under the second if statement, for now rest seems to be working fine. and i just need a solution, that is it. and this doesnt solve it complete ly since it is not running the 2nd recursive call. Can you help me fix that ? it is something about `python` i think @trincot — Ahmed Can Unbay, May 23 '22 at 08:52
Hmmm... Did you see the questions in my comment? Can you come back to them? *"rest seems to be working fine...just need a solution"*: if you are just wondering about a call that is not made, and are not interested in changing the algorithm, then can you please review the tags (this is not Dijkstra's algorithm)? To see why a call is not made, just use a debugger and step through the code, inspect variables to see where the execution goes and why. If however you have a question about the algorithm, let me know. But for debugging, just rely on your debugger. — trincot, May 23 '22 at 09:16
i deleted the tag for `djikstra`, when i analyze the code, i dont know why that part of the code doesnt run at all. it is bus and it has train so it has to enter both if conditions not only the first one Yes need to better with tagging next time @trincot — Ahmed Can Unbay, May 23 '22 at 09:44
So just check really well all variables that are participating in the `if` condition. Please point explicitly *which* `if` condition in your code you feel should have been entered. Did you place a break point on the `if`? Did execution stop there? What value does the expression in the `if` condition have at that moment? This is really basic debugging you should do.... — trincot, May 23 '22 at 09:47
do you see the ```if currentStation == "Bus":``` after ```if currentStation == "Bus" and currentCity in CitiesWithTrain: #check if trainStationExists``` that if doesnt run. it doesnt run anything inside. where it is supposed. as i stated in the question. but the if condition before that runs, and it has the same partial condition. and I dont return anything as well, just running recursive. How to fix this ? it is a simple question — Ahmed Can Unbay, May 23 '22 at 09:58
Sorry I don't understand what you you mean with "this runs" and "doesnt run". There is a difference between an `if` statement that is executed, and an `if` condition that evaluates to true. And I don't know which of the two you refer to. However it is simple: if an `if` statement is executed (this you can see with a break point), then the condition is evaluated (you can evaluate it during debugging). It it evaluates as a truthy value, then the `if` block is entered. If it evaluates to a falsy value, then the `if` block is skipped. There is no magic there. Just debug. — trincot, May 23 '22 at 10:07
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/244951/discussion-between-turmuka-and-trincot). — Ahmed Can Unbay, May 23 '22 at 10:11
İt doesnt evaluateat all. Does not evaluate. İt is supposed to evaluate true, indeed if it did then it would *run*. There is no other condition where it can ‘run’ without evaluating. Yes you dont understand because you dont look at the picture. 4 if statements, if one evaluates true, rest doesnt get evaluated even tho i dont return the function. @trincot — Ahmed Can Unbay, May 23 '22 at 10:11
So, did you put a breakpoint? Did execution stop there? Are you using a debugger? If not, then let's stop the discussion, as that is the first thing to do. — trincot, May 23 '22 at 10:15
I put simple print function right after if statements, didnt run. Evaluation is guaranteed to return true @trincot — Ahmed Can Unbay, May 23 '22 at 10:17
OK, so you are not using a debugger. Let's leave it here. I am moving on. Consider debugging. — trincot, May 23 '22 at 10:17
Since i am already settimg the currentstation to bus on the first recursive call @trincot — Ahmed Can Unbay, May 23 '22 at 10:18
@trincot well i dont have debugging practices on py. Can you help me out with that ? — Ahmed Can Unbay, May 23 '22 at 10:22
You can debug with several tools, e.g. VS Code. See [these answers](https://stackoverflow.com/a/66842058/5459839) — trincot, May 23 '22 at 11:41
@trincot okey i debugged it, after it evaluates the first if condition the first time it runs the functions, it never evaluates the second if condition i stated, only through the recursive call the next time first `if` fails. So to me it feels like i need some asynchrous func there.. but still that doesnt make sense because it never evaluates the second if condition as it runs the first thread. but it has to.. why this happens ? I hope I am clear enough @trincot — Ahmed Can Unbay, May 23 '22 at 11:52
so i debugged and it passes that part of the code without even doing evaluation. it doesnt `run` that if statement. It keeps diving into the recursion without creating simultaneous recursions. so there is nobody who can solve this phonemonen with `python` interpreted language ? @trincot — Ahmed Can Unbay, May 23 '22 at 15:21
I think you are mistaking recursion with parallel computing. A recursive call is no different from any other function call: the statement below that function call will only get executed when that function call *finishes*, i.e. when it has *returned*. As long as that function call is busy -- maybe with calling yet another (or the same) function, the next statement will not yet execute. This is not specific to python. — trincot, May 23 '22 at 15:25
i see, how do i solve this problem then ? i want to keep searching through graph simultaneously, even if not (if there isnt anyhting like that in python) , when that function finishes, it(the first caller thread) still doesnt go on with the next one as you see in the output.. still doesnt make sense @trincot — Ahmed Can Unbay, May 23 '22 at 15:34
Sorry, you must be misunderstanding: when the function returns, it *surely* goes on with the next statement. If that wouldn't be true, no one would be using Python. To be clear: your code just uses one thread. If you want to run code *simultaneously*, then you need to create new threads. This is possible in Python, but is advanced. I sincerely doubt you need that for basic graph traversal. — trincot, May 23 '22 at 15:38
so that means i need to be checking the variables through debugger as you said. well thankyou very much trincot. i respect it.@trincot — Ahmed Can Unbay, May 23 '22 at 16:03

Recursion doesnt run as expected Algorithm For City solving problem

0 Answers0