Comment mettre en œuvre une version récursive de cette fonction

Question

que je dois mettre en œuvre une version récursive de cette fonction:

static void peneira (int m, int v[]) { 
    int f=2, t; 
    while(f<=m){ 
     count_Iteracoes_HeapSort++; 
     if(f<m && v[f] < v[f+1])++f; 
     if(v[f/2] >= v[f]) break; 
     t = v[f/2]; v[f/2] = v[f]; v[f] = t; 
     f *= 2; 
    } 

} 

que je faisais quelque chose comme ceci:

static void peneiraRec(int m,int v[]){ 
    count_Iteracoes_HeapSort++; 
    int f=2,t; 
    if(m<=1) { 
     return; 
    } 
    while(f<=m) { 
     peneiraRec(m - 1, v); 
     if (f < m && v[f] < v[f + 1]) ++f; 
     if (v[f/2] >= v[f]) break; 
     t = v[f/2];v[f/2] = v[f];v[f] = t; 
     f *= 2; 
    } 
} 

Mais cela ne fonctionne pas. Quelqu'un peut-il m'aider?

Cette fonction est une fonction auxiliaire du tri de tas. Je signalerai tout le code

static void 
constroiHeap (int m, int v[]) 
{ 
    int k; 
    for (k = 1; k < m; ++k) {     
     // v[1..k] é um heap 
     int f = k+1; 
     while (f > 1 && v[f/2] < v[f]) { // 5 
     troca (v[f/2], v[f]);   // 6 
     f /= 2;      // 7 
     } 
    } 
} 

static void peneira (int m, int v[]) { 
    int f=2, t; 
    while(f<=m){ 
     count_Iteracoes_HeapSort++; 
     if(f<m && v[f] < v[f+1])++f; 
     if(v[f/2] >= v[f]) break; 
     t = v[f/2]; v[f/2] = v[f]; v[f] = t; 
     f *= 2; 
    } 

} 

void 
heapsort (int n, int v[]) 
{ 
    int m; 
    constroiHeap (n, v); 
    for (m = n; m >= 2; --m) { 
     troca (v[1], v[m]); 
     peneira (m-1, v); 
    } 
} 
int main{ 
    int v0[6] = {0,63726,2323,0,32,236723}; 
    heapsort_rec(5, v0); 
} 

Sortie: v0 = 0,32,2323,63726,236723

Fondamentalement, je besoin de mon entrée est un tableau et la sortie triée doit être le tableau ordely.

J'ai besoin de mettre en œuvre cette fonction Peneira dans une récursif loin

Answer 1

tout d'abord pourquoi appelez-vous peneiraRec avec m-1 comme premier argument. Dans l'implémentation non récursive, m ne change pas, seulement f le fait. Deuxièmement, chaque fois que vous appelez votre fonction, f est réglé sur 2 et vous ne voulez pas cela. Vous voulez que f soit 2 fois sa valeur précédente. Et troisièmement pourquoi utiliser la récursivité de la tête au lieu de la queue. Ma suggestion est de changer la définition de peneiraRec en peneiraRec (int m, int v [], int f). La première fois que vous en aurez besoin, appelez-le avec f = 2 aw son troisième paramètre et après l'appel récursivement comme peneiraRec (m, v, 2 * f).

Answer 2

Toute boucle peut être rendue récursive en transformant le corps de la boucle en une fonction qui prend comme argument la variable de boucle (en plus des variables utilisées à l'intérieur de la boucle). La fonction teste d'abord la variable loop pour voir si la limite a été atteinte, et retourne si elle l'a été. Sinon, il effectue une itération de la boucle, puis s'appelle lui-même avec la nouvelle valeur de la variable de boucle. Typiquement, vous aurez besoin de deux fonctions; la fonction d'étape récursive, et une autre fonction pour appeler l'étape récursive avec la valeur initiale de la variable de boucle.

static void peneira_rec (int f, int m, int v[]) { 
    int t; 
    if(f > m) return; // exit loop 

    count_Iteracoes_HeapSort++; 
    if(f<m && v[f] < v[f+1])++f; 
    if(v[f/2] >= v[f]) return; // exit loop 
    t = v[f/2]; v[f/2] = v[f]; v[f] = t; 
    peneira_rec(f*2, m, v); // loop again 
} 

static void peneira (int m, int v[]) { 
    peneira_rec(2, m, v); // start the loop 
} 

Answer 3

Je ne somenting comme celui-ci après CGSS réponse

void peneiraRec(int m,int v[], int f){ 
    count_Iteracoes_HeapSort++; 
    int t; 
    if(f>m){ 
     return; 
    } 
    if(f<m && v[f] < v[f+1])++f; 
    if(v[f/2] >= v[f]) return; 
    t = v[f/2]; v[f/2] = v[f]; v[f] = t; 
    peneiraRec(m,v,f*2); 
} 

void heapsort_rec(int n, int v[]){ 
    int m; 
    constroiHeap (n, v); 
    for (m = n; m >= 2; --m) { 
     count_Iteracoes_HeapSort; 
     int t=v[1]; v[1]=v[m]; v[m]=t; 
     peneiraRec (m-1, v,2); 
    } 
} 

Et cela fonctionne, je pense que je l'ai fait. Je ne voyais pas ce qui était dans mon visage, seulement f changeait pas m, vraiment merci les gars et désolé pour mon explication stupide, je suis nouveau sur stackoverflow.