Quali sono le considerazioni per determinare se è possibile utilizzare la ricorsione per risolvere un problema?

Question

Quali sono le considerazioni per determinare se è possibile utilizzare la ricorsione per risolvere un problema?

#1 da (16 voti)
#2 da (2 voti)
#3 da (1 voti)
#4 da (0 voti)

11

A volte nelle interviste, posso usare la ricorsione per risolvere un problema (come aggiungere 1 a un numero intero di precisione infinito) o quando il problema si presenta adatto per ricorrere alla ricorsione. A volte, potrebbe essere semplicemente riconducibile all'uso della ricorsione per risolvere i problemi, quindi senza pensare molto, la ricorsione viene utilizzata per risolvere il problema.

Tuttavia, quali sono le considerazioni prima che tu possa decidere che sia adatto per ricorrere alla ricorsione per risolvere un problema?

Alcuni pensieri che ho avuto:

Se usiamo la ricorsione su dati che si dimezzano ogni volta, sembra che non sia un problema ricorrere alla ricorsione, dato che tutti i dati che possono essere contenuti in 16 GB di RAM, o anche un disco rigido da 8 TB, possono essere gestiti dalla ricorsione solo 42 livello profondo. (quindi nessun overflow dello stack (credo che in alcuni ambienti, lo stack può essere profondo 4000, molto più di 42, ma allo stesso tempo, dipende anche da quante variabili locali hai, come ogni stack di chiamate, occupa più memoria se ci sono molte variabili locali, ed è la dimensione della memoria, non il livello, che determina l'overflow dello stack)).

Se calcoli i numeri di Fibonacci utilizzando la ricorsione pura, devi davvero preoccuparti della complessità del tempo, a meno che non memorizzi nella cache i risultati intermedi.

E che ne dici di aggiungere 1 a un numero intero di precisione infinito? Forse è discutibile, come, lavorerai con i numeri che sono di 3000 cifre di lunghezza o di 4000 cifre, così grande da causare un overflow dello stack? Non ci ho pensato, ma forse la risposta è no, non dovremmo usare la ricorsione, ma semplicemente usare un ciclo semplice, perché cosa succede se in alcune applicazioni, il numero deve essere composto da 4000 cifre, per verificare proprietà del numero, ad esempio se il numero è primo o meno.

L'ultima domanda è: quali sono le considerazioni prima di poter decidere di utilizzare la ricorsione per risolvere un problema?

recursion algorithms

posta 太極者無極而生 24.04.2017 - 12:06

fonte

4 risposte

Leggi altre domande sui tag recursion algorithms

Perché utilizzare Eccezione sopra (controllata)? Funziona quando uno sviluppatore è il capo del project manager?

score 16 · Answer 1

Una considerazione è se il tuo algoritmo debba essere una soluzione astratta o una soluzione pratica eseguibile. Nel primo caso, gli attributi che stai cercando sono correttezza e facilità di comprensione per il tuo pubblico di destinazione ¹. In quest'ultimo caso, anche le prestazioni sono un problema. Queste considerazioni possono influenzare la tua scelta.

Una seconda considerazione (per una soluzione pratica) è se il linguaggio di programmazione (o più rigorosamente, la sua implementazione) che stai usando elimina la coda? Senza l'eliminazione chiamata, la ricorsione è più lenta dell'iterazione e la ricorsione profonda può portare a problemi di overflow dello stack.

Si noti che una soluzione ricorsiva (corretta) può essere trasformata in una soluzione equivalente non ricorsiva, quindi non è necessariamente necessario fare una scelta difficile tra i due approcci.

Infine, a volte la scelta tra formulazioni ricorsive e non ricorsive è motivata dalla necessità di dimostrare (in senso formale) le proprietà di un algoritmo. Le formulazioni ricorsive consentono più direttamente la dimostrazione per induzione.

^{1 - Questa include considerazioni come se il pubblico di destinazione ... e questo potrebbe includere i programmatori che leggono codice pratico ... considererebbe uno stile di soluzione "più naturale" rispetto al altro. La nozione di "naturale" varierà da persona a persona, a seconda di come hanno appreso la programmazione o l'algoritmica. (Sfido chiunque proponga la "naturalezza" come criterio primario per decidere di ricorrere alla ricorsione (o meno) per definire la "naturalezza" in termini oggettivi, cioè come la si misura.)}

score 2 · Answer 2

However, what are the considerations before you can decide it is suitable to use recursion to solve a problem?

Durante la scrittura di funzioni in Scheme, trovo naturale scrivere funzioni ricorsive in coda senza pensare troppo.

Durante la scrittura di funzioni in C ++, mi ritrovo a discutere prima di utilizzare una funzione ricorsiva. Le domande che mi pongo sono:

Il calcolo può essere eseguito utilizzando un algoritmo iterativo? Se sì, usa un approccio iterativo.
La profondità della ricorsione può aumentare a seconda della dimensione del modello? Recentemente mi sono imbattuto in un caso in cui la profondità della ricorsione è cresciuta fino a quasi 13000 a causa delle dimensioni del modello. Ho dovuto convertire la funzione per utilizzare un algoritmo iterativo post-rapidità.

Per questo motivo, non raccomanderei di scrivere un algoritmo di attraversamento dell'albero usando le funzioni ricorsive. Non si sa mai quando l'albero diventa troppo profondo per l'ambiente di esecuzione.
La funzione può diventare troppo complessa utilizzando un algoritmo iterativo? Se sì, utilizzare una funzione ricorsiva. Non ho provato a scrivere qsort usando un approccio iterativo, ma ho la sensazione che usare una funzione ricorsiva sia più naturale per questo.

score 1 · Answer 3

Come programmatore C / C ++, la mia considerazione principale è la prestazione. Il mio processo decisionale è qualcosa del tipo:

Qual è la profondità massima dello stack di chiamate? Se è troppo profondo, elimina la ricorsione. Se poco profondo, vai a 2.
È probabile che questa funzione sia un collo di bottiglia del mio programma? Se sì, vai a 3. Se no, mantieni la ricorsione. Se non sei sicuro, esegui un profiler.
Qual è la frazione del tempo impiegato dalla CPU per le chiamate a funzioni ricorsive? Se le chiamate di funzione impiegano molto meno tempo rispetto al resto del corpo della funzione, è ok usare la ricorsione.

score 0 · Answer 4

Per i numeri di Fibonacci, l'ingenua "ricorsione" è completamente stupida. Questo perché porta allo stesso subproblem che viene risolto più e più volte.

In realtà c'è una variazione banale dei numeri di Fibonacci dove la ricorsione è molto efficiente: Dato un numero n ≥ 1, calcola sia fib (n) che fib (n-1). Quindi hai bisogno di una funzione che restituisca due risultati, chiamiamo questa funzione fib2.

L'implementazione è abbastanza semplice:

function fib2 (n) -> (fibn, fibnm1) {
    if n ≤ 1 { return (1, 1) }
    let (fibn, fibnm1) = fib2 (n-1)
    return (fibn + fibnm1, fibn)
}