recursivité

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.

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.

Salut,

Comme l’a dit LudoBike, il manque un return ligne 7.

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

PS: La récursivité, c’est comme la récursivité, en plus simple.