version itérative d'une fonction récursive

[invitec64e4f8e]

Salut à tous,

j'ai beau essayer de rédiger la version iterative de la function suivante :

void f(int n) {
    if(n==1) {
        printf("%d\t",n);
        return;
    }
    f(n-1);
    printf("%d\t",n);
    f(n-1);
    return;
}

mais je suis à court d'idée.

Notamment, le resultat que retourne cette fonction est comme suit :
f(0) -> 1
f(1) -> 121
f(2) -> 1213121
f(3) -> 121312141213121

Est-ce quelqu'un pourrait m'aider ? Merci d'avance.
-----

[Chanur]

Bonjour,

Déjà une remarque : tu devrais tester la fonction, parce qu'elle ne fait pas ce que tu dis.

f (0) va lancer f(-1), f(-2), f(-3) etc. jusqu'à arriver à 1, c'est à dire des milliards de niveaux de récursivité.
Chez moi, ça se dit : "Erreur de segmentation (core dumped)"

f(1) affiche "1" (et non 121)
f(2) affiche "1 2 1" (et non 1213121)
f(3) affiche "1 2 1 3 1 2 1"
...
f(n) affiche "{le résultat de f(n-1)} n {le résultat de f(n-1)}"

Les valeurs affichées sont séparées par des tabulation et la liste se finit par une tabulation, sans retour chariot.

[Dlzlogic]

Bonjour,
Un bon exemple à tester, c'est la fonction factorielle. C'est l"exemple type utilisé pour ce genre de chose.
D'autre part, c'est curieux que vous n'ayez pas, comme Chanur, testé la fonction.

[invitebd98b571]

Bonjour
tout est noyé dans les diverses remarques (plus ou moins justifiées à mon avis)...

f(n) affiche "{le résultat de f(n-1)} n {le résultat de f(n-1)}"

Voila ce qu'il fallait comprendre dans l'algorithme pour répondre à la question (n est supérieur ou égale à 1 était sous entendu).

Maintenant, on peut calculer itérativement f(1), f(2), puis f(3), ... jusqu'à f(n), grâce à une petite boucle

[A voir en vidéo sur Futura]

[imoca]

r <- '';
for i=1..n:
r<- r.str(i-1).r;// . pour contacter
fin de for
print r;

[invitebd98b571]

bon... voilà qui donne (presque) la solution... c'est str(i) qu'il faut concaténer.