Appel d'une fonction récursive

bonjour,

ceci t'aidera sans doute à comprendre:

def fonct(n):
    global d
    d+=1
    print(d*"   ","appel pour n=",n)
    if n < 1:
       x=1
    else:
       x=fonct(n-1) + fonct(n-2)
    print(d*"   ","réponse pour n=",n,":",x)
    d-=1
    return x
d=0
print(fonct(3))

Bonjour

l'idée de yg_be d'ajouter des prints pour tracer les différents appels et niveaux de recursion est bonne.

Mais tes 2 fonctions exemples ne sont pas faciles à appréhender, mais si pour une exécution le calcul est simple.

Les récursions le rendent, disons opaque.

Prenons un exemple pour simple, la fonction prend a et b en paramètre et retourne leur produit.

Elle ne sait pas multiplier, ni faire une boucle.

Pour le besoin de la démo, on ajoute un paramètre "niveau" qui suit la "plongée" dans la recursion (je préfère ça à une variable globale)

L'idée est la suivante, la fonction ajoute a à l'appel d'elle même autant de fois qu'il y a de b.

pour ça, à chaque appel, elle enlève 1 à b. Quand celui-ci est nul, elle n'ajoute plus rien.

def produit(a, b, niveau):
    niveau+=1
    print("Appel : ", niveau)
    if b == 0: #fin de la récursivité
        print("niveau =", niveau, ", b = 0, return 0")
        return 0
    
    #on demande le calcul suivant, on y passe a, b - 1 pour decompter le nombre d'additions et le niveau pour la trace
    intermediaire = produit(a, b - 1, niveau)
    
    print("niveau =", niveau,", b =", b, "return 5 +", intermediaire)
    return a + intermediaire
    
print(produit(5,3,0))

Ce qui donne

Appel :  1
Appel :  2
Appel :  3
Appel :  4
niveau = 4 , b = 0, return 0
niveau = 3 , b = 1 return 5 + 0
niveau = 2 , b = 2 return 5 + 5
niveau = 1 , b = 3 return 5 + 10
15
> 

On voit que la fonction est appelée 4 fois.

Au 4eme appel, b est nul, donc la fonction ne s'appelle plus, elle retourne un premier résultat nul au niveau 3.

Le niveau 3 reçoit donc 0, qu'il ajoute à 5 et le retourne au niveau 2.

Le niveau 2 reçoit 5, qu'il ajoute à 5 et le renvoie au niveau 1.

Le niveau 1 reçoit 10, qu'il ajoute à 5 et le renvoie au programme principal.

Le programme principal affiche 15.

Bonsoir, un réponse un peu plus littéraire.

def fonct(n):
    if n < 1:
       return 1
    else:
       return fonct(n-1) + fonct(n-2)

Pour fonct(3) donc :
1er appel, fonct(2) + fonct(1), on ne peut déterminer aucune de ces 2 valeurs, on décompose, on tente de calculer la plus petite valeur puisque c'est dans ce sens que la récursivité cessera.
- Pour fonct(1), on obtient fonct(0) + fonct(-1), les deux valeurs sont inférieures à 1.
calcul = 1 + 1

- Pour fonct(2): on a fonct(1) + fonct(0), soit fonct(1) + 1, on a déjà préalablement calculé fonct(1) qui vaut 2
calcul = 1 + 1 + 2 + 1
On obtient bien 5.   
 

def fonct(x):
    if x < 3:
       return 1
    else:
       return 3 * fonct(x-2)

Pour fonct(7) donc :
1er appel, cela doit retourner 3 * fonct(5)
On garde seulement le 3 * puiqu'on ne connaît pas encore le résulat de fonct(5).
calcul = 3 *
2nd appel, cela doit retourner 3 * fonct(3), pareil, on garde encore que le 3 *
calcul = 3 * 3 *
3ème appel, cela doit une nouvelle fois rappeler la fonction, 3 * fonct(1)
calcul = 3 * 3 * 3 *
dernier appel, on est en dessous de 3, on obtient alors 1
calcul = 3 * 3 * 3 * 1

Bonjour,

def fonct(n):
    if n < 1:
       return 1
    else:
       return fonct(n-1) + fonct(n-2) 

C'est quasiment une suite de Fibonacci (à ceci prêt que normalement fonct(0) devrait valoir 0 et pas 1). Ceci dit la logique ne change pas vraiment.

Je pense que pour percevoir la logique de se qui se passe, il vaut mieux le voir sous l'angle de la programmation dynamique. C'est en gros une manière d'intégrer une notion de mémoire dans un appel récursif.

Donc ici, si tu mémorises les valeurs de fonct(0) et fonct(1), tu peux calculer fonct(2) et plus généralement si tu connais fonct(i) et fonct(i+1), tu peux calculer fonct(i+2). On pourrait donc imaginer que tu remplisses un tableau qui mémorise ces valeurs par i croissant pour faire le calcul "à la main".

L'appel récursif suit la même logique, mais au lieu d'aller par valeur de i croissante, il "remonte" les valeurs de i. Le calcul de f(i+2) déclenche le calcul de f(i+1) et de f(i), qui font de même à leur tour jusqu'à atteindre un critère d'arrêt (en l'occurrence i < 1).

On voit cependant que lorsqu'on appel f(i+2), il engendre le calcul de f(i+1) et de f(i) de manière indépendantes. Or c'est un peu dommage car f(i+1) aura lui même besoin de f(i) qui n'est pas mémorisé. C'est là où la programmation dynamique entre en jeu. Elle consiste à mémoriser les valeurs déjà calculées pour éviter d'avoir à les recalculer.

Dans le code ci-dessous, on mémorise dans d les termes calculés au fur et à mesure. Si on le trouve c'est parfait, on évite tous les calculs nécessaire pour le (re)calculer. Si on ne trouve pas le terme désiré, c'est qu'on ne l'a pas calculé jusqu'à présent, et on le calcule de manière opportuniste.

def fonct_dyn(n: int, d: dict) -> int:
    r = d.get(n)
    if r is None:
        if n < 1:
            r = 1   
        else:   
            r = fonct_dyn(n - 1, d) + fonct_dyn(n - 2, d)
        d[n] = r
    return r

def fonct(n: int) -> int:
    d = dict()
    r = fonct_dyn(n, d)
    print(d)
    return r

print(fonct(3))

Exécution : le dictionnaire ci-dessous recense les termes de la suite qui ont été calculés (ci dessous, fonct(0) = 1, fonct(-1) = 1, etc...), puis on affiche la valeur demandée (fonct(3) = 5)

{0: 1, -1: 1, 1: 2, 2: 3, 3: 5}
5

Tu peux adapter ta seconde fonction récursive de la même manière pour dérouler le raisonnement.

Bonne chance

Merci à tous pour votre aide!

Bon, le sujet est encore bien "nébuleux" pour moi.

Pour contextualiser un peu, j'essaye d'apprendre le programme de 1ère/terminale NSI dans le cadre d'un concours. Le soucis, c'est que je travaille sur cette matière tout seul, en partant de 0 sur le sujet, sans prof (le devis de chez Acadomia est clairement hors budget pour moi),... Du coup ce n'est pas toujours évident!
Et pour le coup, le chapitre traitant des fonctions récursives fait partie du programme de terminale alors même que je n'ai pas encore achevé celui de 1ère. Il doit certainement me manquer encore quelques outils pour pouvoir arriver à répondre à ce genre d'exercices, car j'avoue que certaines logiques m'échappent encore dans vos réponses.
Mais je m'accroche!

Pour préciser aussi, lors du concours, pour traiter les questions, on ne dispose que d'une feuille et d'un stylo.

Merci encore en tout cas!

Bonjour

prenons un exemple qui sera peut-être plus clair, la somme des n premiers entiers.

S = 1 + 2+ ... + n - 1 + n

Contrairement à mon exemple de produit, les nombre vont changer à chaque appel.

Pour écrire un code qui ferait ce calcul, la première approche est une boucle (un while par exemple)

def SommeNPremiersWhile(n : int):
    s = 0
    i = 1
    while(i<=n):
        s += i
        i += 1
    
    return s
    
print(SommeNPremiersWhile(9))

Voilà qui m'affiche 45.

Si on s'attache à décrire ce qui se passe

la fonction est appelée avec la consigne de faire la somme des 9 premiers nombres entiers
    on initialise la somme à 0
    on initialise la variable d'itération à 1
    
    on rentre dans la boucle
        première itération
            s = 0 + 1 = 1
            i passe à 2
        deuxième itération
            s = 1 + 2 = 3
            i passe à 3
        troisième itération
            s = 3 + 3 = 6
            i passe à 4
        quatrième itération
            s = 6 + 4 = 10
            i passe à 5
        etc...
        neuvième itération
            s = 36 + 9 = 45
            i passe à 10
        10 est supérieur à 9 => on sort de la boucle
    
    On retourne 45

On peut aussi faire ce code de manière récursive.

def SommeNPremiersRecursif(n : int):
    if n == 1:
        return 1

    return n + SommeNPremiersWhile(n - 1)    
        
print(SommeNPremiersRecursif(9))

Voilà qui m'affiche aussi 45

Si on s'attache à décrire ce qui se passe

la fonction est appelée avec la consigne de faire la somme des 9 premiers nombres entiers 

(appel 1) 9 n'est pas 1, on appelle donc la fonction avec 8
(appel 2) 8 n'est pas 1, on appelle donc la fonction avec 7  
(appel 3) 7 n'est pas 1, on appelle donc la fonction avec 6 
(appel 4) 6 n'est pas 1, on appelle donc la fonction avec 5
(appel 5) 5 n'est pas 1, on appelle donc la fonction avec 4 
(appel 6) 4 n'est pas 1, on appelle donc la fonction avec 3 
(appel 7) 3 n'est pas 1, on appelle donc la fonction avec 2 
(appel 8) 2 n'est pas 1, on appelle donc la fonction avec 1 

(appel 9) Oh joie ! 1 est 1. Cet appel à la fonction retourne donc 1
L'appel 8 reçoit 1 l'ajoute à 2, et retourne 3
L'appel 7 reçoit 3, l'ajoute à 3 et retourne 6
L'appel 6 reçoit 6, l'ajoute à 4 et retourne 10
L'appel 5 reçoit 10, l'ajoute à 5 et retourne 15
L'appel 4 reçoit 15, l'ajoute à 6 et retourne 21
L'appel 3 reçoit 21, l'ajoute à 7 et retourne 28
L'appel 2 reçoit 28, l'ajoute à 8 et retourne 36
L'appel 1 reçoit 36, l'ajoute à 9 et retourne 45

Comme tu peux le constater, on peut décrire avec un papier et un crayon le comportement de cette fonction.

Note, pour qu'une fonction récursive fonctionne, il y a 2 conditions fondamentales

• Il faut une condition d'arrêt
• Chaque appel récursif converge vers cette condition

Ma condition d'arrêt c'est n == 1 (je pars du principe que n est toujours positif...) et à chaque appel, je décrémente n, qui finit donc par arriver à 1

Quand n vaut 1, les appels récursifs cessent et là, on commence à faire le calcul.

Chaque appel reçoit une valeur de son "enfant", fait son bout de calcul et retourne un résultat à son parent.

Bonjour,

Pour donner un autre exemple montrant ce que l'on peut faire avec de la récursion:

afficher une chaine de caractères en partant de la fin:

def inverse(s,k):

    if(k != len(s)):
        inverse(s,k+1)
        print(s[k], end = '')

inverse('tniop a ritrap tuaf li riruoc ed tres en neiR',0)

Ici, les caractères sont affichés lors du dépilage des appels successifs de la fonction, d'où l'inversion:

on fait des appels successifs avant le print et à la fin en sortant du dernier appel, on tombe sur le print

à ce niveau, k=le dernier caractère, ensuite, après ce print à nouveau on sort de la fonction à ce stade,

donc on retombe après l'appel, donc à nouveau sur le print, avec la valeur qu'avait k à ce niveau, etc...