Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Funzioni ricorsive vs cicli
Forum - C/C++ - Funzioni ricorsive vs cicli

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
Roby94 (Member)
Guru


Messaggi: 1170
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 17:12
Lunedì, 02/11/2015
Buonasera, eccoci qui con un nuovo quesito prestazionale. A parere vostro, per un implementazione di una funzione generica che necessita di un operazione ripetuta n volte che implementazione secondo voi è preferibile, un ciclo while o un metodo ricorsivo, in che casi? e sopratutto perché?
(Premetto che i ragionamenti che vorrei sentire siano riferiti a macchine single thread, quindi niente operazioni esterne al codice preso in considerazione)
Grazie.

PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6379
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 17:54
Lunedì, 02/11/2015
Un codice ricorsivo fa largo uso di stack che non è una risorsa abbondante. Quindi è un approccio che non va usato a cuor leggero. In molti casi è meglio l'approccio iterativo.


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1170
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 18:42
Lunedì, 02/11/2015
D'accordo, grazie nessuno. Vorrei aggiungere una terza opzione, una funzione con ciclo interno che richiama ad ogni ciclo una seconda funzione.

Inoltre vorrei proporre una casistica che di recente ho affrontato ma a cui ancora ripenso chiedendomi se l'implementazione sia la "migliore".
In questo caso ho usato dei template per definire delle funzioni di scrittura e lettura della EEPROM di un AVR, queste si rifanno quindi a 2 algoritmi uno per leggere e uno per scrivere i dati.
I templete sono stati compilati 10 volte ciascuno. Ora continuo a pensare, in un caso in cui viene usata una sola dichiarazione del templeate nel codice il tutto funziona bene e non si notano particolari sprechi di memoria, ma se vengono richieste 2 o piu combinazioni di tipi questo codice va a ripetersi piu volte nella piccola memoria dell'AVR. Ora il principio di funzionamento è molto semplice, viene accettato il dato in ingresso ed eseguito un ciclo while in base alla sua dimensione, all'interno del ciclo viene gestita la scrittura del singolo ottetto. Cosi come è proposto forse sarebbe meglio avere una funzione che scrive un singolo ottetto e tutte le funzioni di contorno vadano a richiamare quella in un ciclo while, questo escludendo a priori la funzione ricorsiva che richiami se stessa fino all'esaurimento degli ottetti. Scegliendo questa strada mi troverei però a richiamare diverse volte una funzione all'interno di un altra, il risparmio di memoria secondo voi giustifica l'approccio? penso che la velocità di scrittura non sia un aspetto critico quanto il sovra consumo di memoria flash, voi cosa pensate?

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 22:19
Lunedì, 02/11/2015
Mah in realtà quando sei sui Microcontrollori fai ciò che ti consente di risparmiare più flash. Ma nel caso in cui la flash Abbondi e i tempi computazionali siano inaccettabili corri ai ripari "sprecando" flash, mai stack, perché su quelle CPU lo stack è di 6/8 livelli, quindi un approccio ricorsivo è da evitare nel modo più assoluto.

PM Quote
Avatar
ZioCrocifisso (Member)
Pro


Messaggi: 135
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 1:22
Martedì, 03/11/2015
Chiamare una funzione in un ciclo non è rilevante quanto una funzione ricorsiva, perché nel primo caso la memoria sullo stack viene allocata e deallocata ad ogni chiamata, mentre nelle funzioni ricorsive la memoria rimane tra una chiamata e l'altra. In realtà, anche se sostituisci correttamente un loop con una funzione ricorsiva, quasi sicuramente sarà efficiente quanto il loop, perché i compilatori (con le ottimizzazioni attivate) generalmente ottimizzano le tail calls, ma chiaramente non ha senso affidarsi a questa ottimizzazione se puoi essere sicuro con un loop.

PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 8:14
Martedì, 03/11/2015
Potrà essere solo l'impressione di uno che programma "a spanne", ma l'uso dei cicli mi dà una maggiore sensazione di chiarezza e di controllo su quel che sto facendo. In più (ma potrebbe essere che parlo a vanvera), non è che tutto quel creare e distruggere fa perdere tempo con l'esecuzione di istruzioni per allocazioni/inizializzazioni e deallocazioni "invisibili"?


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 14:17
Martedì, 03/11/2015
In realtà per quanto riguarda Pic e avr un ciclo e una funzione ricorsiva impiegano lo stesso tempo (se scrivi a mano in assembly il ciclo) quindi l'unica differenza è l'utilizzo di stack.

PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6379
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 16:08
Martedì, 03/11/2015
@Roby94

Se devi scrivere su EEPROM la velocità non è la prima cosa a cui devi pensare, dato che è un dispositivo "lento" rispetto al resto.
In quel caso è corretto usare funzioni che trattano "stringhe" e sottofunzioni che trattano "caratteri/byte".

E' assolutamente da evitare la ricorsione nel codice micro.


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1170
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 19:56
Domenica, 08/11/2015
Testo quotato

Postato originariamente da nessuno:

@Roby94

Se devi scrivere su EEPROM la velocità non è la prima cosa a cui devi pensare, dato che è un dispositivo "lento" rispetto al resto.
In quel caso è corretto usare funzioni che trattano "stringhe" e sottofunzioni che trattano "caratteri/byte".

E' assolutamente da evitare la ricorsione nel codice micro.



Si, il mio era solo un esempio, in questo caso la velocità non è determinante, mi vengono mente interazioni con una seriale senza HW dedicato.
Per questa volta opererò con le funzioni e sotto funzioni, e mi terrò sempre a distanza dalle ricorsive.
Grazie

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo