Récursivité, suites par récurrence et Syracuse

Version imprimable

Bonjour. :D

Je suis un élève de Terminale et je travaille actuellement sur la récursivité.
Je suis confronté à un exercice que je n'arrive pas à finir après avoir essayé tout ce que je trouvais pertinent à faire. Ici, mon code me renvoit toujours le message d'erreur suivant :

Code:

RuntimeError: maximum recursion depth exceeded in comparison

par rapport aux lignes 6, 9 puis encore, puis encore 9.... et la ligne 5 une fois que Python ait atteint le maximum de profondeur de récursivité (je ne poste pas le code exact de l'erreur ici sinon ça prendrait un bon millier de lignes).

Voici l'intitulé de l'exercice :

"Soit u_n la suite d'entiers définie par :

u_n+1 = u_n/2 si u_n est pair,
= 3 x u_n + 1 sinon,

Avec u₀ un entier quelconque plus grand que 1.
Ecrire une fonction récursive syracuse(u_n) qui définie les valeurs successives de la suite u_n tant que u_n est plus grand que 1.
La conjecture de Syracuse affirme que, quelle que soit la valeur de u₀, il existe un indice n dans la suite tel que u_n = 1. Cette conjecture défie toujours les mathématiciens."

Et voici le fameux code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 from math import * def syracuse(u_n): valeurs=[] if (u_n)%2==0: return syracuse(u_n-1)/2 valeurs.append(syracuse(u_n)/2) else: return 3*syracuse(u_n-1)+1 valeurs.append(3*syracuse(u_n-1)) print(syracuse(10))
A noter qu'à cause du confinement dû au Coronavirus, mon niveau en Python est assez maigre. :aie:

Il me faudrait d'urgence une réponse avant ce soir, s'il-vous-plaît, sinon mon devoir recevra une note proche de la bulle. 8O

11/10/2020, 13h38
wiztricks

Salut,

Vous avez omis de traduire le tant que u_n est plus grand que 1.... et donc la pile des appels ne s'arrête que parce que Python y mets le hola.

Citation:

Envoyé par Jyggalag

me faudrait d'urgence une réponse avant ce soir, s'il-vous-plaît, sinon mon devoir recevra une note proche de la bulle. 8O

Fonction récursive ou simple boucle, c'est la réalisation de la condition d'arrêt qui fait que çà ne part pas en "boucle" et qu'on peut appeler çà "algorithme" (parce que çà se termine).
Sans condition d'arrêt, c'est pas la bulle mais la tête à toto;-)

- W
11/10/2020, 13h52
Jyggalag

Salut,

Citation:

Vous avez omis de traduire le tant que un est plus grand que 1.... et donc la pile des appels ne s'arrête que parce que Python y mets le hola.

J'ai essayé d'y remédier en rajoutant ceci juste avant le if :

Code:

while syracuse(u_n)>1:

Mais la même erreur de profondeur de récursivité maximale est réapparue. Donc j'ai essayé avec u_n au lieu de syracuse(u_n), et une nouvelle erreur est apparue, ne concernant plus cette ligne mais la ligne 6 (devenue 7 vu que j'ai rajouté le while, mais sur le code de mon premier post, c'est la ligne 6) de mon code :

Code:

TypeError: unsupported operand type(s) for /: 'NoneType' and 'int'

Est-ce juste ma boucle while qui doit être corrigée, ou le problème vient-il d'ailleurs ?
11/10/2020, 15h30
wiztricks

Salut,

Citation:

Envoyé par Jyggalag

Mais la même erreur de profondeur de récursivité maximale est réapparue. Donc j'ai essayé avec u_n au lieu de syracuse(u_n), et une nouvelle erreur est apparue

Si vous ajoutez une condition, c'est pour arrêter la descente récursive et les appels à la fonction. Donc si la première instruction de la fonction sera d'appeler cette fonction sans condition... c'est que vous essayez tout et n'importe quoi sans trop réfléchir avant.

Donc vous n'avez pas le choix, il faut tester u_n.

Après réfléchissez: tester u_n > 1 c'est soit pour appeler la fonction encore une fois soit pour retourner une valeur dans le cas contraire. Par défaut une fonction retourne None et c'est bien ce que vous récupérez.
A vous de savoir quoi retourner dans ce cas.

- W

Des petites confusions. 2 propositions :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def syracuse1(u_n):
    if u_n > 1:
        print(u_n, end=' - ')
        if u_n%2==0:
            return syracuse1(u_n//2)
        else:
            return syracuse1(3*u_n+1)
    return u_n
 
def syracuse2(n, t=0):
    if n > 1:
        print(n, end=' : ')
        return syracuse2(3*n+1 if n%2 else int(n/2), t+1)
    return n
 
print(syracuse1(3))
print(syracuse2(3))

Bonjour

Citation:

Envoyé par Jyggalag

(je ne poste pas le code exact de l'erreur ici sinon ça prendrait un bon millier de lignes).

Oui, l'ensemble complet de la pile des appels (qui est définie à 1000 justement)
Citation:
Envoyé par Jyggalag
Et voici le fameux code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 from math import * def syracuse(u_n): valeurs=[] if (u_n)%2==0: return syracuse(u_n-1)/2 valeurs.append(syracuse(u_n)/2) else: return 3*syracuse(u_n-1)+1 valeurs.append(3*syracuse(u_n-1)) print(syracuse(10))
Et à quoi sert le tableau "valeurs" ? (qui en plus ne peut pas être rempli puisque la fonction s'arrête juste avant !!!)

Citation:

Envoyé par Jyggalag

A noter qu'à cause du confinement dû au Coronavirus, mon niveau en Python est assez maigre. :aie:

Le confinement empêche-t-il de télécharger un tutoriel et le lire et s'exercer aux TP qui sont écrits ?

Citation:

Envoyé par Jyggalag

Il me faudrait d'urgence une réponse avant ce soir, s'il-vous-plaît, sinon mon devoir recevra une note proche de la bulle. 8O

Peut-être. Mais bon, d'une part on n'est pas là pour faire tes devoirs (ce serait d'ailleurs une tricherie vis à vis de ceux qui tentent l'exerice de façon honnête), d'autre part quand tu seras dans la vie tu ne pourras pas aller sur les forums demander qu'on te fasse ton job (enfin tu pourras toujours demander c'est plutôt les réponses qui seront amusantes). En plus c'est contraire aux règles du forum. Et enfin ce devoir ne t'a pas été donné aujourd'hui à 12h57. Si ?

Donc généralement, l'approche récursive commence par définir et écrire la condition d'arrêt. Ce n'est pas obligatoire (dans certains cas on peut la mettre après) mais ça simplifie généralement l'écriture.
Et une fois la condition d'arrêt posée, on peut alors écrire l'appel récursif
Exemple avec la factorielle
Code:

1 2 3 4 5 def facto(n): if n == 0: return 1 return n * facto(n-1) print(facto(5))
Citation:

Envoyé par Jyggalag

J'ai essayé d'y remédier en rajoutant ceci juste avant le if : while syracuse(u_n)>1 mais la même erreur de profondeur de récursivité maximale est réapparue. Donc j'ai essayé avec u_n au lieu de syracuse(u_n), et une nouvelle erreur est apparue, ne concernant plus cette ligne mais la ligne 6 (devenue 7 vu que j'ai rajouté le while, mais sur le code de mon premier post, c'est la ligne 6) de mon code

Comme dans "Astérix, le combat des chefs", avec Panoramix qui a oublié comment faire la potion magique et qui met dans sa marmite tout ce qui lui tombe sous la main en espérant tomber juste...

Citation:

Envoyé par Jyggalag

Est-ce juste ma boucle while qui doit être corrigée, ou le problème vient-il d'ailleurs ?

La récursivité permet justement de ne pas avoir à écrire de boucle while (c'est l'appel récursif qui produit l'effet de bouclage) Donc le pb se situe au niveau de la réflexion. Et en plus des exemples de Syracuse il y en a plein le net...