[OT] Programmare ricorsivamente

[daniele_dll]

Beh, metti caso che l'utente inserisce, per fare una prova, un valore tipo 1952347 ti ritroverai possibilmente con uno stack overflow

Possibilmente quei linguaggi li ovviano al problema in altro modo, magari nelle specifiche di implementazione del linguaggio è prevista la gestione di queste situazioni (per fare un esempio cretino quando lo stack va per esaurisrsi lo spostano in memoria e lo reinizializzano inserendo come primo elemento una chiamata che srotolerà lo stack precedente e poi la seconda serie di registri riferiti alla chiamata che non ci stava nello stack precedente)

UPDATE:
l'esempio precedente, scritto utilizzando un'iterazione

int isPari(int x)
{
    while(x >= 1)
    {
        x -= 2;
    }
    return x;
}

o la forma compatta

int isPari(int x)
{
    while((x -= 2) >= 1) {}
    return x;
}

#############
altro update
##############

guardate che differenza c'è tra i tempi di esecuzione di codice che fa la stessa cosa, senza ovviamente nessun tipo di ottimizzazione

CON RICORSIONE

[root@alpha admin]# time ./test 230792
230792
Dispari!
isPari e' stata richiamata 115397 volte

real    0m0.006s
user    0m0.003s
sys     0m0.003s

SENZA RICORSIONE

[root@alpha admin]# time ./test 230792
230792
Pari!

real    0m0.002s
user    0m0.001s
sys     0m0.001s

Con un minimo di ottimizzazioni
gcc -Wall -O3 -fomit-frame-pointer -pipe -funroll-loops -o test test.c

SENZA RICORSIONE

[root@alpha admin]# time ./test_noric 500000000
500000000
Pari!
isPari e' stata richiamata 0 volte

real    0m0.023s
user    0m0.021s
sys     0m0.001s

CON RICORSIONE

[root@alpha admin]# time ./test_siric 500000000
500000000
Dispari!
isPari e' stata richiamata 250000001 volte

real    0m0.255s
user    0m0.255s
sys     0m0.000s

(nota: senza -O3 non c'arrivava a quel valore perché andava in seg fault prima)

Come si diceva prima, un aumento di chiamate aumenta esponenzialmente anche il carico dei processori e della memoria

*****

Ovviamente si parla di ricorsioni che hanno un numero consistente di chiamate, però rimane il fatto che comunque il tempo di esecuzione aumenta esponenzialmente non tanto per via delle operazioni che sono uguali ma per lo più per via del sovraccarico dovuto dal funzionamento delle chiamate ricorsive

Ora, ripeto, non è che siccome i sistemi iterativi, in media, sono più performanti vanno usati ovunque, anzi, è normale che se devo cercare "piccole" liste o non mi interessa la performance il codice si semplifica un pò

[menphisx]

Originariamente inviato da LeleFT
PS: Aggiungo una nota alla discussione... esistono linguaggi in cui l'iterazione non esiste e tutto viene fatto attraverso la ricorsione. Scheme (derivato da Lisp) e Prolog sono due esempi.

Si ma sono linguaggi funzionali, sono un'altra storia e di solito non molto performanti

[XWolverineX]

Originariamente inviato da menphisx
Si ma sono linguaggi funzionali, sono un'altra storia e di solito non molto performanti

Infatti.
Nell'uso di questi linguaggi le performances (pignole) sono l'ultima cosa da pretendere.

[LeleFT]

Originariamente inviato da XWolverineX
Infatti.
Nell'uso di questi linguaggi le performances (pignole) sono l'ultima cosa da pretendere.

A parte il fatto che Prolog non è un linguaggio funzionale, ma un linguaggio Logico (sono due cose enormemente differenti), nessuno voleva mettere in discussione l'efficienza...

Ciao.