Discussion :

[nadia85]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[WhiteCrow]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void puiss(int x, int n, int *res);

[valentin03]

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

[nadia85]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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».

[AbsoluteLogic]

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).

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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

Salutations

[nadia85]

Bonsoir,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[nadia85]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Guesset]

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 ).

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

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Par

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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 C :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[anapurna]

salut

en pascal c'est plus parlant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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;

[WhiteCrow]

@anapurna : mais la fonction est non terminale car il y a une multiplication au retour de l'appel récursif.

[Guesset]

Bonjour Anapurna,

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

Comme le Pascal est plus parlant on voit plus vite les problèmes :

• Le type Expanded permet d'éviter l'overflow . 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

[AbsoluteLogic]

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[nadia85]

Bonjour,

Oui ça fonctionne très bien.

Merci beaucoup