programmation ardue fonction récursive en C Fermé

Question

Bonjour, je travaille actuellement sur une fonction récursive qui croit trop vite pour pouvoir être calculée par n'importe quel ordinateur, c'est la fonction d'ackermann, voici son code C:

long ackermann(int m, int n){
  if(m==0){
    return(n+1);
  }else if ((n==0){
    return ackermann(m-1, 1);
  }else{
    return ackermann(m-1, ackermann(m,n-1));
  }
}

Mon but est d'utiliser une technique dont le principe est simple (et connu) pour diminuer le nombre de récursions: Je stocke les résultats déjà calculés dans un tableau, je vérifie si la valeur a déjà été calculée, si oui je récupère la valeur dans le tableau, si non je la calcule et la stocke dans le tableau. J'ai essayé de traduire en C mon idée, je souhaiterais votre avis s'il vous plait :

long ackermann(int m, int n, long tableau[][4]){
  long var;
  if(m==0){
    return(n+1);
  }else if ((n==0){
    return ackermann(m-1, 1, tableau);
  }else{
    if(tableau[m][n] == 0){
      var=ackermann(m,n,tableau);
      tableau[m][n]=var;
    }else{
    return tableau[m][n];
  }
}

Le tableau est déclaré dans le main. Que pensez vous de ma fonction?
merco bcp.

Char Snipeur · Answer

n vaut entre 0 et 4 ?
Je croi détecter une boucle infini.
si m!=0 et n!=0 et tableau[m][n]==0 alors tu appels la fonction "ackermann(m,n,tableau)" c'est à dire que tu n'as rien changé.
il faut : ackermann(m,ackermann(m,n-1,tableau),tableau) je pense.
Je mettrait tout en "long" aussi. 
Par contre, ackermann(m,n-1,tableau) pourrait renvoyer un truc plus grand que 3 et posé un problème de taille de tableau non ?

Char Snipeur · Answer

à peu près la même chose. Je suis déjà plus d'accord avec le 4 où tu l'as mis.
par contre le dernier else !!!
Si ton tableau est différent de 0 (si tu l'as rempli donc) alors tu calcul la valeur et tu la retournes !?
ce que je verrai :

long ackermann(long m, long n, long tableau[4][])
{
    long var;
    if(m==0){
        return(n+1);
    }else if ((n==0){
        return ackermann(m-1, 1, tableau);
    }else{
        if(tableau[m][n] == 0){
            var=ackermann(m,ackermann(m,n-1,tableau),tableau); 
            tableau[m][n]=var;
        }else{
            return tableau[m][n];
        }
    }// accolade manquante
} 

e dois stocker chaque appel dans le tableau, donc tu es d'accord que pour stocker une valeur de A(m,n), je dois faire (je précise qu'à la base toutes les cases du tableau sont à 0):

if(tableau[m][n] == 0){
var=ackermann(m,n,tableau);
tableau[m][n]=var

jusqu'ici es tu d'accord avec ça?

absolument pas !
Je persiste sur ton var=, tu tombe sur une boucle infinie. Fait un test à la main pour t'en convaincre.

Char Snipeur · Answer

oui, mais les retours sont dans des if.
met un return -1 à la fin. En plus ça permet de traiter les erreurs inattendus.

Char Snipeur · Answer

Non, pas de mélange de case, mais en C les tableaux commencent à "0" !
donc :
for(i=0;i<65534;i++){
for(j=0;j<5;j++){
tableau[j][i]=0;
}
}

pour les tableaux, comme tu connais la taille autant la donner à chaque fois.

Char Snipeur · Answer

2 solutions : soit tu débug en mettant des print pour connaitre les valeurs soit tu fais une fonction prorpre. Comme tu utilises un tableau, il faut tester voir si tu ne dépasses pas. const int mMAX=5,nMAX=65534; long ackermann(long m, long n, long tableau[mMAX][nMAX]){ if(m>=mMAX || n>=nMAX) //traitement particulier de l'erreur. peut être même ajouter (on ne sais jamais) if(m<0 || n<0) // etc.

fiddy · Answer

Bonjour,

Tu n'as pas besoin de parcourir ton tableau pour le remplir à 0. Ca se fait facilement lors de la déclaration. De plus, l'utilisation du tableau est mal implémenté et tu as fait une erreur dans la définition de la fonction d'Ackermann.
var=ackermann(m,ackermann(m,n-1,tableau),tableau); 
Il s'agit de m-1 en premier argument. Ce qui change tout...

Niveau algorithmique, j'aurais plutôt vu un truc du genre :

#include <stdio.h>

long ackermann(long m, long n, long tableau[][65534]) {
    if(m==0 && tableau[n][n]==0) tableau[0][n]=n+1;
    else if(n==0 && tableau[m][n]==0) tableau[m][0]=ackermann(m-1,1,tableau);
    else if(tableau[m][n]==0) tableau[m][n]=ackermann(m-1,ackermann(m,n-1,tableau),tableau);
    return tableau[m][n];
}

int main(void) {
    long tableau[5][65534]={{0}};

    printf("%ld
", ackermann(2,3,tableau));

    return 0;
}


Ensuite, faudrait voir pour mieux gérer la taille du tableau, quitte à faire de l'allocation dynamique.

Cdlt,

Programmation ardue fonction récursive en C

6 réponses

Discussions similaires