[C] somma interi con ricorsione - migliorare programma già fatto

[Freaxxx]

#include <stdio.h>

int sommaTraInteri(int myA, int myB, int*, int*);

int main(){
    int mA=12;
    int mB=16;
    int sum=0;
    int cur=mA+1;
    printf("\n%d\n",sommaTraInteri(mA,mB,&sum,&cur));
}

int sommaTraInteri(int myA, int myB, int *sum, int *cur){
    if(*cur>myA && *cur<myB){
        *sum=*sum+*cur;
        *cur=*cur+1;
        sommaTraInteri(myA,myB,sum,cur);
    } else return *sum;
}

ho appena fatto questo programma che effettua la somma di tutti gli interi che si trovano tra i due interi passati alla funzione come argomento ( quindi non considera gli estremi nella somma ), il punto è che funziona perfettamente, ma non mi piace stilisticamente e per come è scritto, vorrei migliorarlo un po', ma sarà l'ora, ma non mi vengono molte idee, voi ne avete?

[Kenger]

Codice PHP:

#include <stdio.h>

int sommaTraInteri(int myA, int myB, int);

int main(){
    int mA=12;
    int mB=16;
    int cur=mA+1;
    
    printf("\n%d\n",sommaTraInteri(mA, mB, cur));
}

int sommaTraInteri(int myA, int myB, int cur) {
    if(cur>myA && cur<myB)
        return cur + sommaTraInteri(myA, myB, cur+1);
} 


Spero non sia un qualche genere di compito

[Freaxxx]

Originariamente inviato da Kenger

Codice PHP:

#include <stdio.h>

int sommaTraInteri(int myA, int myB, int);

int main(){
    int mA=12;
    int mB=16;
    int cur=mA+1;
    
    printf("\n%d\n",sommaTraInteri(mA, mB, cur));
}

int sommaTraInteri(int myA, int myB, int cur) {
    if(cur>myA && cur<myB)
        return cur + sommaTraInteri(myA, myB, cur+1);
} 


Spero non sia un qualche genere di compito

tranquillo che sono esercitazioni a caso che sto rabattando da internet giusto per fare qualcosa.

in pratica hai tolto il passaggio per riferimento e fatto un "trenino" di int con il return, sembra più corta in effetti ...

EDIT: il programma ha una logica errata, mi da un risultato sbagliato

[Kenger]

Puoi darmi qualche dettaglio in più? Con l'esempio 12-16 mi da 42 che è la risposta giusta se non ho capito male il problema.

[Freaxxx]

Originariamente inviato da Kenger

Puoi darmi qualche dettaglio in più? Con l'esempio 12-16 mi da 42 che è la risposta giusta se non ho capito male il problema.

io ho controllato la logica e mi sembra corretta, ma il programma compilato sotto codeblocks mi da 58 come valore, preso pari pari e soltanto incollato e compilato.

non riesco a capire, provo a compilarlo "a mano" con gcc.

[Freaxxx]

sempre 58 mi da.

edit: in pratica include nella somma anche l'estremo mB, il risultato dovrebbe essere 42, ma viene 58 cioé 42+16

[WarDuck]

int Summer( int a, int b )
{
   if (a>=b) return 0;
   if (b-a==1) return 0;
   if (b-a==2) return a+1;

   return a+1 + Summer(a+1, b);
}

Scritto al volo, non l'ho testato molto...

[Kenger]

Non ho codeblocks qua ma usando questo

http://codepad.org/txumHNmt

Mi dà il risultato giusto. Non sò che dire.

[Kenger]

Prova così sennò.

Codice PHP:

int sommaTraInteri(int myA, int myB, int cur) { 
    if(cur<=myA || cur>=myB) 
        return 0;

    return cur + sommaTraInteri(myA, myB, cur+1); 
} 


[Freaxxx]

adesso installo linux da qualche parte e provo con altre versioni di gcc, ho paura che questo sia un bug ...

[Freaxxx]

compilato sotto la beta1 attuale di Ubuntu

tux@tux-VirtualBox:~$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6.1/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.1-7ubuntu2' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++,go --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-7ubuntu2)

e sempre 58 mi da, inizio a pensare male di gcc

[shinya]

C'è da dire che la tua versione iniziale mi pare sia tail-recursive (involontariamente, credo), mentre le altre che ho visto successivamente mi pare non lo siano.
Io farei una roba tipo (se non ho scritto stronzate):

#include <stdio.h>

int SumRangeAux(int a, int b, int accum) {
  return a >= b ? accum : SumRangeAux(a + 1, b, accum + a);
}

int SumRange(int a, int b) {
  return SumRangeAux(a + 1, b, 0);
}

int main() {
  int a = 12, b = 16;
  printf ("%d\n", SumRange(a, b));
  return 0;
}

[Kenger]

No, hai ragione, la mia non è tail-recursion. La soluzione iniziale immagino possa essere definita tail-recursion ma non usa minimamente la ricorsione, si passa direttamente il puntatore al risultato in giro. Non ha per niente senso così.

Se vuoi qualcosa con la tail-recursion l'unica cosa che mi viene in mente è

Codice PHP:

#include <stdio.h> 

int sommaTraInteri(int myB, int, int); 

int main(){ 
    int mA=12; 
    int mB=16; 
     
    printf("\n%d\n",sommaTraInteri(mB, mA+1, 0)); 
} 

int sommaTraInteri(int myB, int cur, int tot) { 
    if(cur>=myB) 
        return tot; 

    return sommaTraInteri( myB, cur+1, tot + cur); 
} 


Almeno usi i valori di ritorno ma mi sembra abbastanza brutto.

La mia versione finale è:

Codice PHP:

#include <stdio.h> 

int sommaTraInteri(int myA, int myB); 

int main(){ 
    int mA=12; 
    int mB=16; 
     
    printf("\n%d\n",sommaTraInteri(mA+1, mB)); 
} 

int sommaTraInteri(int myA, int myB) { 
    if(myA==myB) 
        return 0; 

    return myA + sommaTraInteri( myA + 1 , myB ); 
} 


[VICIUS]

C'è una formula facile da ricordare che permette di sommarli senza ricorsione o cicli. Però tiene conto anche degli estremi quindi nel tuo caso ci si deve ricordare di aggiungere e sottrarre 1.

#include <stdio.h>

int sum(int from, int to) {
	return ((to * to) - (from * from) + from + to) / 2;
}

int main(int argc, char** argv) {
	printf("%d", sum(12 + 1, 16 - 1));
}

[shinya]

Originariamente inviato da Kenger

Almeno usi i valori di ritorno ma mi sembra abbastanza brutto.

Sì beh non è tanto questione di bello o brutto. Sono due soluzioni molto diverse in termini di complessità di spazio, ed è bene conoscere questi aspetti, soprattutto se uno sta facendo esercizi per imparare.

[AnonimoVeneziano]

Originariamente inviato da Kenger

Puoi darmi qualche dettaglio in più? Con l'esempio 12-16 mi da 42 che è la risposta giusta se non ho capito male il problema.

EDIT : non ho letto bene

[AnonimoVeneziano]

Originariamente inviato da Freaxxx

tranquillo che sono esercitazioni a caso che sto rabattando da internet giusto per fare qualcosa.

in pratica hai tolto il passaggio per riferimento e fatto un "trenino" di int con il return, sembra più corta in effetti ...

EDIT: il programma ha una logica errata, mi da un risultato sbagliato

La logica è sbagliata almeno per un motivo : Nel caso "if" tu non ritorni un valore, infatti con capisco come faccia a funzionarti in alcuni casi (forse piglia qualcos'altro dallo stack ... che a volte potrebbe essere anche la cosa giusta o il registro EAX usato per il valore di ritorno viene usato anche per la somma e quindi rimane impostato all'uscita dell'ultima "sommaTraInteri" oppure ancora viene impostato dal return del caso else ...)

#include <stdio.h>

int sommaTraInteri(int myA, int myB, int*, int*);

int main(){
    int mA=12;
    int mB=16;
    int sum=0;
    int cur=mA+1;
    printf("\n%d\n",sommaTraInteri(mA,mB,&sum,&cur));
}

int sommaTraInteri(int myA, int myB, int *sum, int *cur){
    if(*cur>myA && *cur<myB){
        *sum=*sum+*cur;
        *cur=*cur+1;
        sommaTraInteri(myA,myB,sum,cur);
    } else return *sum;
}

La linea in grassetto dovrebbe essere:

 return sommaTraInteri(...blah) ;

[WarDuck]

Originariamente inviato da shinya

Sì beh non è tanto questione di bello o brutto. Sono due soluzioni molto diverse in termini di complessità di spazio, ed è bene conoscere questi aspetti, soprattutto se uno sta facendo esercizi per imparare.

La cosa più importante prima è scrivere qualcosa di corretto, tail o no viene dopo, molto dopo.

Inoltre per come la vedo io, se devi scrivere codice tail-recursive, a meno che non ti venga naturale farlo, tantovale usare direttamente l'iterazione.

La via più naturale, per come la vedo io, è usare la ricorsione classica con lo stack delle chiamate, anche se questo può essere meno efficiente, ma secondo me è utile per capire bene il meccanismo.

[shinya]

Originariamente inviato da WarDuck

La cosa più importante prima è scrivere qualcosa di corretto, tail o no viene dopo, molto dopo.

Su questo non ci piove.

Originariamente inviato da WarDuck

Inoltre per come la vedo io, se devi scrivere codice tail-recursive, a meno che non ti venga naturale farlo, tantovale usare direttamente l'iterazione.

La via più naturale, per come la vedo io, è usare la ricorsione classica con lo stack delle chiamate, anche se questo può essere meno efficiente, ma secondo me è utile per capire bene il meccanismo.

No ma io non sto difendendo una soluzione piuttosto che un'altra. Dico solo che è bene sapere riconoscere e capire pro e contro di entrambi gli approcci. Altrimenti si finisce a calcolare fibonacci con complessità esponenziale solo perché "il prof. mi ha insegnato che la ricorsione è così".
E alla fine in termini pratici dipende dal linguaggio: in C usare la ricorsione in questo modo non è il modo idiomatico di esprimere questo algoritmo. In Haskell magari la situazione cambia... e allora è bene sapere la differenza tra i vari approcci e non solo avere "qualcosa che funziona".

[AnonimoVeneziano]

Originariamente inviato da shinya

In Haskell magari la situazione cambia... e allora è bene sapere la differenza tra i vari approcci e non solo avere "qualcosa che funziona".

lol :: Int -> Int -> Int
lol a b | a < (b-1) = (a+1) + k
         | a >= b-1 = 0
         where k = lol (a+1) b

main = do
           putStrLn $ show $ lol 20 25