recursivité

python 3

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonsoir chères amis. Au faite je voudrais développer une fonction récursive qui permet de démontrer si un graphe possède un circuit.

pour cela je représente mon graphe avec un dictionnaire comme ci-dessous:

1
dico = {"a": ["b", "c"], "b": [], "c": ["d"], "d": ["a"], "e": []}

Chaque nœud du graphe représente ma clef et ces successeurs représente la valeur. s’il y a un circuit sa sous entend qu’on peut partir de par exemple "a" pour revenir a "a".

voici ma fonction récursive:

1
2
3
4
5
6
7
8
def circuit(somtest, som, marq, dico):
     marq.append(som)
     for i in dico[som]:
          if i == somtest:
               return True
          if i not in marq:
               circuit(somtest, i, marq, dico)
     return False

marq: est une liste permettant de marquer les sommets parcourus

somtest: est un sommet

som: est un sommet

j’utilise l’algorithme de parcours en profondeur. par exemple si je lance :

1
2
marq = []
circuit("a", "a", marq, dico)

Mon problème c’est que lorsque l’algorithme rencontre le return True il ne retourne pas immédiatement il continue a s’exécuter jusqu’à a venir retourner le false de la fin.

Merci d’avance.

À la recherche de la connaissance.

+0 -0

Si la fonction ne s’arrête pas c’est qu’elle ne rencontre jamais le return. Essaye d’afficher des messages si tu passes dans tes conditions et d’afficher les variables à chaque tour, ça permet de localiser le problème.

Edit

Dans une fonction récursive, il faut retourner la valeur que retourner la fonction que tu lance, sinon tu as ce problème. J’aurais bien voulu développer un peu plus et mettre le bon vieil exemple de la fonction factorielle mais je suis sur mon portable.

Édité par LudoBike

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0
Auteur du sujet

J’ai vue mon erreur. Merci😁😁 Or j’avais bien regarder avant de posté. J’ai un peu honte même. Mais merci à vous.

Édité par watanga96

À la recherche de la connaissance.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte