Rendre terminale une fonction récursive

Version imprimable

Bonjour,

J'ai la fonction récursive puissance qui calcule x à la puissance n en distinguant les deux cas: n est pair et n est impair.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
int puis(int x, int n)
{
   int y;
    if(n==0)
     { return 1;
     }
    else if(n%2==0)
         {
             n=n/2;
             y=puis(x,n);
             return y*y;
         }
    else
    {
        n=n/2;
        y=puis(x,n);
        return x*y*y;
    }
}

Comment rendre cette fonction terminale?

Merci d'avance

10/11/2022, 22h20
WhiteCrow

Bonjour,

et si tu essayais de rajouter un paramètre pour le résultat (technique classique) ?
Par exemple avec un prototype comme :

Code:

void puiss(int x, int n, int *res);
11/11/2022, 13h12
valentin03

Bonjour,
Tu peux y mettre un compteur, et quand le compteur est "up" ou "down", tu sort de la boucle.

Bonjour,

Justement il faut rajouter un paramètre à la fonction récursive qui sera un accumulateur:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
 
int puis(int x, int n, int y)
{
 
    if(n==0)
     { return 1;
     }
    else if(n%2==0)
         {
             n=n/2;
             return puis(x,n,y*y);
         }
    else
    {
        n=n/2;
        return puis(x,n,x*y*y);
    }
}

Pourriez-vous m'aider à trouver le problème?

Merci d'avance

11/11/2022, 19h36
WhiteCrow

as-tu bien lu le prototype que je t'ai proposé ?
là ce n'est pas un problème d'algo mais plus de langage C … l'accumulateur doit «être passé par référence et non par copie pour pouvoir récupérer sa valeur modifiée».

Citation:

Envoyé par WhiteCrow

là ce n'est pas un problème d'algo mais plus de langage C … l'accumulateur doit «être passé par référence et non par copie pour pouvoir récupérer sa valeur modifiée».

Ce n'est pas obligé, en partant du code de nadia85, on peut retourner la valeur qui nous intéresse (valeur finale de l'accumulateur) plutôt que de faire un paramètre par référence (qui est justement une notion dépendant du language).
Citation:
Envoyé par nadia85
Bonjour,

Justement il faut rajouter un paramètre à la fonction récursive qui sera un accumulateur:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int puis(int x, int n, int y) { if(n==0) { return 1; } else if(n%2==0) { n=n/2; return puis(x,n,y*y); } else { n=n/2; return puis(x,n,x*y*y); } }
Pourriez-vous m'aider à trouver le problème?
Ben du coup la réponse est dans mon commentaire à WhiteCrow :p

13/11/2022, 19h59
Guesset

Bonjour,

Le premier problème est que le troisième paramètre n'est pas géré comme un accumulateur. Les résultats doivent remonter de l'appel le plus profond et se cumuler lors de la remonté ce qui suppose soit un argument comme spécifié par WhiteCrow soit une variable globale accessible (heureusement on a ici une chaîne linéaire d'appels).

L'autre problème est qu'on ne peut pas mélanger un retour fonctionnel avec une variable de retour. Enfin si on peut, mais cela ne sert à rien puisqu'alors deux mécanismes ayant le même objectif sont sollicités simultanément. Par ailleurs, cela induit des nœuds au cerveau : par exemple la seule valeur de retour est 1 et elle ne se combine plus avec les étapes appelantes comme c'était le cas dans la récursivité simple.

Enfin, mais peut être suis-je hors problème, une fonction non récursive fera très bien le boulot (et elle sera terminale par définition 8-)

Salutations

Bonsoir,

Oui absolument il faut retourner la valeur de l'accumulateur sinon ça n'a pas de sens.
J'ai rectifié le code
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int puissance(int x, int n, int y) { if (n==0) return y; else if(n%2==0) return puissance(x,n/2,y*x); else return puissance(x,n/2,x*x*y); }
pour n=4 et n=5 le résultat d'exécution est juste (le programme retourne 16 et 32). Sauf que pour n=1, n=2 et n=3 le résultat est erroné.

Pourriez-vous m'aider à résoudre ce problème?

Merci d'avance

Bonsoir,

Cette version donne des valeurs correctes dans le cas où n est impair: pour n=1 res=2 , pour n=3 res=8 et pour n=5 res=32
mais pour le cas où n est pair c'est faux
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int puissance(int x, int n, int y) { if (n==0) return y; else if(n%2==0) { return puissance(x,n/2,y*y); } else return puissance(x,n/2,x*y*y); }
Pourriez-vous m'aider à résoudre ce problème?
Merci d'avance

Bonjour,

Le code reste très mélangé entre fonction récursive et procédure (void f() ) récursive, ce qui ne présume pas d'une solution rapide. C'est pourquoi je propose une solution qui, pour être utile, doit être comprise (à supposer que je n'y ai pas inclus d'erreur :D ).

Quand on passe à un retour par variable, il suffit, par exemple, de remplacer :
Code:

1 2 3 4 5 ... n = n/2; y = puis(x,n); return y*y; ...
Par
Code:

1 2 3 4 5 ... n = n/2; puis( x, n, r); *r = (*r) * (*r); ...
Ce qui donne en reprenant le code récursif initial et en évitant les répétitions :
Code:

1 2 3 4 5 6 7 8 void puis(int x, int n, int *r) { if(n) { // idem n != 0 puis(x, n / 2, r); *r = (*r) * (*r); if(n & 1) *r *= x; // idem n % 2 ou odd(n) } else *r = 1; // idem n == 0 }
En C++ l'usage de &r permettrait une écriture plus lisible de type r = r * r.

On remarque que cet algorithme (sous cette forme ou la forme initiale) ne traite pas correctement un cas. Lequel ?

Salutations

salut

en pascal c'est plus parlant

Code:

1
2
3
4
5
6
7
8
 
function puissance (base : extended; expo : integer ) : extended ;
begin
  if expo=0 then
     Result:=1
  else
    Result := base∗puissance (base,expo −1);
end;

15/11/2022, 18h38
WhiteCrow

@anapurna : mais la fonction est non terminale car il y a une multiplication au retour de l'appel récursif.
15/11/2022, 18h53
Guesset
Bonjour Anapurna,

Citation:

Envoyé par anapurna

...en pascal c'est plus parlant...

Comme le Pascal est plus parlant on voit plus vite les problèmes :oops: :
- Le type Expanded permet d'éviter l'overflow 8-). Il a une précision de 64 bits sur la mantisse (comme un uint64_t). Il implique de passer par les flottants ce qui diminue les performances.
- L'algorithme proposé n'implémente pas en récursif celui de Dijkstra utilisé par la PO. Il présente une complexité en O(n) au lieu de O(ln(n)).
- La question de rendre la fonction terminale reste à traiter.
Salut

Bon, j'avoue que ça ne se fait pas directement de passer à une fonction terminale. Dans mon cas, je suis allé chercher la réponse ailleurs sur internet.
Malheureusement, vu que je n'ai pas appliqué moi-même la méthode pour trouver la solution, je ne suis pas en mesure de servir de guide, mais seulement de donner directement la réponse :
Code:

1 2 3 4 5 6 7 8 9 10 11 int puissance(int x, int n, int y) { if (n == 0) return y; if (n%2 == 0) return puissance(x*x, n/2, y); else return puissance(x*x, n/2, x*y); } // A appeler avec : puissance(x, y, 1)
En revanche, je peux expliquer pourquoi cette solution fonctionne. Pour ça, je vais utiliser le principe d'invariant de boucle. Bon, là il n'y a pas de boucle, mais une récursion terminale, c'est le même principe.
Mon invariant est le suivant : (x ^ n) * y

Au 1er appel, y vaut 1, donc l'invariant vaut x^n, c'est-à-dire la valeur que l'on souhaite calculer.
Si n est pair, l'invariant de l'itération suivante vaut (x' ^ n') * y' = ((x * x) ^ (n / 2)) * y = ((x ^ 2) ^ (n / 2)) * y = (x ^ (2 * n / 2)) * y = (x ^ n) * y. L'invariant est respecté.
Si n est impair, l'invariant de l'itération suivante vaut (x' ^ n') * y' = ((x * x) ^ ((n - 1) / 2)) * (x * y) = (x ^ (2 * (n - 1) / 2)) * x * y = (x ^ ((n - 1) + 1)) * y = (x ^ n) * y. L'invariant est respecté.
Quand n arrive à 0, l'invariant vaut (x ^ 0) * y = 1 * y = y. Et puisque c'est un invariant, y vaut donc la valeur qu'on avait initialement : x ^ n

16/11/2022, 09h58
nadia85

Bonjour,

Oui ça fonctionne très bien.

Merci beaucoup