Discussion :

[steph_ntic]

Bonjour,
J'aimerai écrire une fonction récursive me permettant de calculer xⁿ pour x réel et n entier naturel en utilisant la définition récursive suivante :
xⁿ = 1 pour n = 0,
xⁿ = (x^(n/2))² pour n pair,
xⁿ = xⁿ⁻¹.x pour n impair.

Merci de m'apporter votre aide.

[baragouine]

Peut-être que je n'ai pas compris, mais je ne vois rien de récursif dans ce que tu demandes.
D’après ce que j'ai compris c'est un code qui ressemble à:

Code :

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

1
2
3
4
5
6
7
 
float lucas(float x, unsigned n)
{
  if (n == 0) return (1);
  if (n & 1) return (x * pow(x, n - 1));
  return (2 * pow(x, n / 2));
}

Bref la fonction ne s'appelle pas elle même.

[steph_ntic]

Merci Baragouine pour ta réponse, je viens de porter une modification au sujet.
J'ai effectivement écrire la fonction de façon normal mais j'aimerai l'écrire d'une autre façon(récursive)

[baragouine]

Je comprends mieux, d'ailleurs je dois admettre que c'est un bon petit exo à faire.

[steph_ntic]

Oui bien intéressant j'avoue

[baragouine]

Finalement cette exo est tellement simple que le seul moyen de t'aider (que j'ai trouver) c'est de te donner le code.
Il suffit simplement de traduire ton énoncer en code:

lucas: (x : réel, n : entier naturel) -> réel
si n = 0 renvoie 1
si n est impaire renvoie lucas(x, n - 1);
renvoie lucas(x, n / 2) * lucas(x, n / 2);

Je ne vois rien de compliquer.

[steph_ntic]

renvoie lucas(x, n / 2) * lucas(x, n / 2);

n paire dans ce cas? ouais plutôt simple j'ai pas eu le flair

[baragouine]

Oui n paire dans ce cas. En tout cas bonne chance pour la suite (si il y en a une).
Et tu peux optimiser soit en stockant la valeur, soit en utilisant pow (pour élever au carré) histoire de ne pas faire deux fois la même chose.

[steph_ntic]

Merci beaucoup pour ton aide

[Sve@r]

Bonjour

Je comprends mieux, d'ailleurs je dois admettre que c'est un bon petit exo à faire.

En C probablement. Parce qu'en Python ça va pas super loin...

Code python :

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

1
2
3
4
def lucas(n, p):
	if p == 0: return 1
	return n * lucas(n, p-1) if p & 1 else lucas(n, p//2) ** 2
# lucas()

[Bousk]

renvoie lucas(x, n / 2) * lucas(x, n / 2);

Ceci fera 2 fois l'opération. Si n est petit ce n,est pas très grave, sinon tu vas effectuer beaucoup plus/trop d'opérations.
Perso je ferais ça plus ça:

Code :

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

1
2
3
4
5
6
7
float power(float value, unsigned int p)
{
  if (p == 0) return 1;
  if (p == 2) return value * value;
  if (p % 2 == 1) return value * power(value, p-1);
  return power(power(value, p/2), 2);
}

[Sve@r]

Ceci fera 2 fois l'opération....Perso je ferais ça plus ça

Mmmmoui...Toutefois tu invoques quand-même un appel de fonction et un test supplémentaire juste pour éviter de multiplier un résultat par lui-même. Est-ce vraiment optimum comme rendement ?

Code :

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

1
2
3
4
5
6
float power(float value, unsigned int p) {
  if (p == 0) return 1;
  if (p % 2) return value * power(value, p-1);
  float f=power(value, p/2);
  return f*f;
}

...

[Bousk]

Mmmmoui...Toutefois tu invoques quand-même un appel de fonction et un test supplémentaire juste pour éviter de multiplier un résultat par lui-même. Est-ce vraiment optimum comme rendement ?

Aucune idée, en pratique j'aurais fait comme ta dernière réponse.
Mais dans le cadre d'un exercice, je préfère faire apparaître la puissance de 2.

[foetus]

Est-ce vraiment optimum comme rendement ?

Juste pour t'embêter , avec des fonctions avec un return final, mais elle n'est pas réentrante

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
21
22
23
float lucas(float value, unsigned int p) {
    float tmp;
 
    if (p == 0) {
        tmp = 1;
    } else
        tmp = lucas_1(value, p, &tmp);
    }
 
    return tmp;
}
 
// XXX : tmp never NULL
float lucas_1(float value, unsigned int p, float* tmp) {
    if (p % 2) {
        (*tmp) = (value * lucas_1(value, (p - 1), tmp);
    } else {
        (*tmp) = lucas_1(value, (p / 2), tmp);
        (*tmp) = (*tmp) * (*tmp);
    }
 
    return (*tmp);
}

[Sve@r]

Juste pour t'embêter

Oui, c'est d'ailleurs à ça qu'on te reconnait

avec des fonctions avec un return final, mais elle n'est pas réentrante

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
float lucas(float value, unsigned int p) {
    float tmp;
 
    if (p == 0) {
        tmp = 1;
    } else
        tmp = lucas_1(value, p, &tmp);
    }
 
    return tmp;
}

Euh ouais... La fonction reçoit l'adresse d'une variable (donc à priori elle va la modifier durant son exécution) mais cette variable est ensuite écrasée par le retour de la fonction !!!
Là j'ai... peur

@steph_ntic
fais pas attention, on déconne, on s'amuse, mais surtout ne prends pas exemple sur nos codes. Enfin si, tu peux prendre exemple sur les miens car ils sont une référence mais n'utilise surtout pas ceux de foetus

[steph_ntic]

J'apprend vraiment de tout ça.