Recursive issue in Python with array

Question

I am developing a recursive function. The code is quick and dirty for the moment but before optimizing it I am facing an issue.

Once recursive function call is going out (I mean my algo is going backward), the case_courante variable is popped up from the stack to the previous value, but this is not the case for arrays dernier_match and tour. I don't understand why.

Here is my code:

#!/usr/bin/python
temps_min=21
temps_max=45
nb_time_slot=245

categorie=[[6,6,6,4,4,2,2,99],[6,6,6,4,4,2,2,99],[6,6,6,4,4,2,2,99],[3,3,3,2,2,2,99],[3,3,3,2,2,2,99],[4,4,4,4,2,2,99],[6,6,6,2,2,2,99],[6,6,6,2,2,2,99],[6,6,6,2,2,2,99],[6,6,6,2,2,2,99],[1,1,1,1,1,1,1,1,1,1,1,1,1]]
dernier_match_depart=[0]*10
case_courante_depart=0
tour_depart=[0]*10
echeancier =[None]*(nb_time_slot+10)
profondeur =0

#function
def choix(prof, case_courante, dernier_match, tour):
        global categorie,temps_min,temps_max,nb_time_slot,echeancier
        for i in range (0,10):
                print ("Profondeur:", prof)
                print(i)
                if (dernier_match[i] == 0):
                        for x in range (case_courante,case_courante + categorie[i][tour[i]]):
                                echeancier[x] = i
                        case_courante = case_courante + categorie[i][tour[i]]
                        dernier_match[i] = case_courante
                        tour[i] = tour[i] + 1
                        print echeancier
                        choix(prof+1, case_courante, dernier_match, tour)
                print ("case courante:", case_courante)
                print ("tour", tour)
                print ("dernier_match",dernier_match)
                if (categorie[i][tour[i]] != 99 and dernier_match[i]+temps_min < case_courante and dernier_match[i]+temps_max > case_courante and case_courante<nb_time_slot):
                        print ("if principal\n")
                        print ("slots dans ce tour",categorie[i][tour[i]])
                        for x in range (case_courante,case_courante + categorie[i][tour[i]]):
                                echeancier[x] = i
                        case_courante = case_courante + categorie[i][tour[i]]
                        dernier_match[i] = case_courante
                        tour[i] = tour[i] + 1
                        print echeancier
                        choix(prof+1, case_courante, dernier_match, tour)
                for a in range (0,9):
                        if (categorie[a][tour[a]] != 99):
                                break
                        else:
                                if (a == 9):
                                        print ("Solution trouvee\n")
                                        print (echeancier)
                                        exit()
#main
choix(0,case_courante_depart,dernier_match_depart, tour_depart)

quamrana · Accepted Answer · 2018-04-12 11:34:47Z

1

Its because you reassign case_courante:

case_courante = case_courante + categorie[i][tour[i]]

but you only modify elements of tour and dernier_match:

dernier_match[i] = case_courante
tour[i] = tour[i] + 1

so case_courante keeps referring to different immutable integers, but the others always refer to their original lists and never refer to anything else.

Update:

It looks like your recursive function has two recursive call sites (both the same):

choix(prof+1, case_courante, dernier_match, tour)

My initial guess (because I don't know the required functionality) is to pass copies of the lists:

choix(prof+1, case_courante, dernier_match[:], tour[:])

edited Apr 12, 2018 at 11:34

answered Apr 12, 2018 at 10:15

quamrana

39.5k13 gold badges57 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

quamrana Over a year ago

Your question never established what is correct. Do you want to go back to the previous states of variables on return like case_courante does now, or do you want to retain the current state like tour and dernier_match do now?

darrepac Over a year ago

Sorry to have been not clear: I want to go back to the previous state of variables (like is doing case_courante)

Collectives™ on Stack Overflow

Recursive issue in Python with array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related