UVa 3n + 1 cas récursif Stack Overflow

Question

im essayant de résoudre ce premier challange mais je coincé, j'aime programme rapide, donc je décidé d'utiliser la méthode récursive pas itération

malheureusement, lorsque l'entrée est grand entier (100000> entrée> 1000000), son s'écraser souvent

donc je déboguer, et il indique l'erreur de débordement de pile

s'il vous plaît aidez-moi, je ne sais pas quoi faire, ive essayé de changer le type de données non signé long, int non signé, etc, mais rien ne fonctionne

ici est mon code, im utilisant ANSI C

#include "stdio.h" 

int cek(int n) { 
    return n % 2; 
} 

int fung(int n,int c) { 
    if (n == 1) { 
     return c; 
    } 
    if (!cek(n)) { 
     return fung(n/2,++c); 
    } 
    else { 
     return fung((n*3)+1,++c); 
    } 
} 

int comp(int i,int j,int tmp) { 
    int temp; 
    if (i == j) 
     return tmp; 
    temp = fung(i,1); 
    if (temp > tmp) 
     return comp(++i,j,temp); 
    else 
     return comp(++i,j,tmp); 
} 

int main() { 
    int i,j,tmp; 
    while (scanf("%d %d",&i,&j)) { 
     if (i > j) { 
      tmp = i; 
      i = j; 
      j = tmp; 
     } 
     printf("%d %d %d\n",i,j,comp(i,j,0)); 
    } 
    return 0; 
} 

PS: désolé pour mon stupidité, im vraiment un débutant @ _ @

Answer 1

pas un expert en C, mais en général il y a une pile d'appel limite de profondeur imposée par le compilateur. Probablement vous pouvez changer cela avec un drapeau de compilateur, mais cela ne résoudra pas votre problème. Rendre l'algorithme itératif au lieu de récursif le corrigera.

Les algorithmes récursifs ne vont pas plus vite que les itératifs, habituellement. Mais ils sont généralement plus agréables à comprendre. (= plus élégant)

Answer 2

La récursion ne devrait pas être plus rapide que l'itération, et en fait, elle sera probablement plus lente. La pile d'appel a une taille limitée, et si votre récursion est plus profonde, vous ne pouvez rien y faire. Surtout dans le problème de Collatz, il n'y a aucun moyen de dire à l'avance combien de pas vous aurez besoin. Réécrivez ceci en utilisant une méthode itérative à la place.

(Si votre compilateur effectue l'optimisation des appels de queue, la récursivité peut toujours fonctionner, mais TCO n'est pas requis par le standard, donc il conduira au code non-portable.) Et apparemment, votre compilateur n'optimise pas cet appel.

Answer 3

Bon les gars, je l'ai trouvé !!!

donc c'est mon code, je l'utilise encore récursion mais seulement pour la fung boucle intérieure(),

je ne suis pas vraiment impressionné de celui-ci, parce que son besoin de 0,5 s à compter entrée 1 et 1000000, quelqu'un Code Outhere peut le faire en 0 sec, LOL

i changer la maquette en boucle externe() avec la méthode itérative,

regarder ici

#include "stdio.h" 
/*#include "windows.h"*/ 

int cek(int n) { 
    return n % 2; 
} 

unsigned int fung(unsigned int n,unsigned int c) { 
    if (n == 1) return c; 
    if (!cek(n)) return fung(n/2,++c); 
    else return fung((n*3)+1,++c); 
} 

/* 
Above recursion will looked like this in iterative method 
int func(int n) { 
    int c=1; 
    while (n != 1) { 
     c++; 
     if (n % 2 == 0) 
      n=n/2; 
     else 
      n=(n*3)+1; 
    } 
    return c; 
} 
*/ 

/*Outer Loop*/ 
int iter(int i,int j) { 
    int tmp1=0,tmp2; 
    while (i <= j) { 
     tmp2 = fung(i,1); 
     if (tmp1 < tmp2) 
      tmp1 = tmp2; 
     i++; 
    } 
    return tmp1; 
} 

int main() { 
    unsigned int i,j,s,f; 
    while (scanf("%d %d",&i,&j)) {   /*UVa Standard, infinite loop*/ 
     /*s = GetTickCount();*/ 
     printf("%d %d %d",i,j,iter(i,j)); 
     /*f = GetTickCount(); 
     printf("%lu\n",f-s);*/ 
    } 
    return 0; 
}