Come verificare se la ricorsione o l'iterazione è la migliore per un particolare programma?

Question

Nel mio college, mi è stato chiesto di scrivere un programma JAVA per la serie di Fibonacci. Ho usato la ricorsione per scrivere quel programma.

Ma il docente asst ha detto che il mio algo non è efficiente e mi ha chiesto di analizzare. Ha aggiunto che per convenzione l'iterazione è adatta a quel programma rispetto alla ricorsione.

Come analizzare il nostro algoritmo? Come verificare la complessità dello spazio e del tempo sia in iterazione che in ricorsione? Proprio in quel momento ho scoperto che queste cose sono importanti quanto la CORRETTEZZA DI UN PROGRAMMA.

Answer 1

Come thumbrule:

• ricorsione è facile da capire per gli esseri umani. Ma è basato sullo stack e lo stack è sempre una risorsa finita.
• L'iterazione è sequenziale e al tempo stesso è più facile eseguire il debug. Ma a volte può portare ad algoritmi di difficile comprensione che possono essere facilmente fatti tramite la ricorsione.

Quindi, ogni volta che il numero di passaggi è limitato a un numero gestibile piccolo, è possibile effettuare la ricorsione. Come avrai la certezza che lo stack non traboccherà mai e allo stesso tempo il codice di ricorsione è compact and elegant.

Se si desidera esplorare più questi potrebbe aiutare. Recursion vs loops e Recursion or Iteration?

Modifica Come rilevato dalla @MrP, alcuni special ricorsioni, possono essere ottimizzate alcuni compilatori.

Answer 2

Non ha nulla a che fare con la complessità dell'algoritmo: quando si utilizza la ricorsione - ogni chiamata crea un nuovo frame sullo stack - quindi se la ricorsione è troppo profonda si potrebbe incorrere in StackOverflow :)

Utilizzando l'iterazione - si sta eseguendo un ciclo (potenzialmente) sullo stesso spazio (ignorando il parametro valori precedenti) che è più veloce e più sicuro dalla prospettiva StackOverflow.

Answer 3

Ti suggerisco di seguire il collegamento http://nptel.iitm.ac.in/courses.php?disciplineId=106 e di trovare alcune lezioni di Progettazione e analisi degli algoritmi. Il suo concetto molto basilare di algoritmi di progettazione. Buona fortuna.

Answer 4

Il problema più grande della serie Fibonacci è la complessità temporale dell'algoritmo, quando si utilizza la ricorsione semplice, si ricreerà tutto e si eseguirà un doppio lavoro. Questo perché quando si calcola fib (n) utilizzando

int fib(int n) { 
    if (n < 2) { return 1; } 
    return fib(n-1) + fib(n-2) 
} 

sarete calcolando fib (n-1), che calcola fib (n-2) e fib (n-3). Ma per il calcolo di fib (n), si calcolerà già fib (n-2). Per migliorare questo, è necessario memorizzare i risultati temporanei. Questo di solito è più semplice usando l'iterazione e partendo da i = 0 fino a n. In questo modo è possibile memorizzare facilmente gli ultimi due risultati ed evitare di calcolare gli stessi valori più e più volte.

Un modo semplice per vedere se un algoritmo è efficiente è cercare di risolverlo per alcuni esempi sempre più difficili. Puoi anche calcolarlo in modo più accurato. Prendi l'esempio di Fibonacci sopra. Chiamare fib (n) richiederebbe la complessità O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1 (prendiamo solo 1 per l'aggiunta).Supponiamo che O(fib(0)) = O(fib(1)) = 1. Questo significa O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9. Come puoi vedere, questa serie salirà più in fretta della stessa serie di Fibonacci! Ciò significa una quantità enorme di complessità crescente. Quando avresti un algoritmo iterativo con un ciclo for da 0 a n, la tua complessità scalerebbe nell'ordine di n, che sarebbe molto meglio.

Per ulteriori informazioni, consultare la notazione grande.