Come posso studiare meglio un problema per determinare se la ricorsione può / deve essere usata?

Question

Come posso studiare meglio un problema per determinare se la ricorsione può / deve essere usata?

#1 da (10 voti)
#2 da (1 voti)
#3 da (0 voti)

5

In alcuni casi, non riesco a vedere che un problema può essere risolto con il metodo divide et impera. Per dare un esempio specifico, quando si studia il problema del find max sub-array, il mio primo approccio è quello di forzare la forza usando un doppio loop per trovare il subarray massimo. Quando ho visto la soluzione utilizzando l'approccio divide et impera basato sulla ricorsione, l'ho capito ma ok. Da parte mia, però, quando ho letto per la prima volta la dichiarazione del problema, non pensavo che la ricorsione fosse applicabile.

Quando studi un problema, c'è qualche tecnica o trucco per vedere che un approccio basato sulla ricorsione (cioè dividi e conquista) può essere usato o meno?

recursion algorithms

posta user10326 28.10.2011 - 11:18

fonte

3 risposte

Leggi altre domande sui tag recursion algorithms

Se una storia è de-scopata durante l'iterazione, allora cosa fare con la sua stima / dimensione? Quando si decompone una funzione grande, come posso evitare la complessità dalle sottofunzioni extra?

score 10 · Answer 1

Per me, credo che un problema sia un buon candidato per la ricorsione se un sottoinsieme più piccolo di questo problema possa essere risolto più facilmente o ovviamente.

Un semplice esempio: parola conta tutti i file che terminano con ".txt" in una cartella che include le sue sottocartelle.

e se avessi un file? (facile: conta le parole che),
e se avessi una cartella? (facile con (1) disponibile: genera un elenco di file, applica (1) quindi somma i risultati),
Cosa succede se le cartelle hanno sottocartelle? (Recurse utilizzando (2) (che utilizza (1) )

Un altro approccio potrebbe essere il "pattern matching": alcuni problemi simili, con problemi ben noti che sono stati risolti con la ricorsione, appaiono. Esempio ancora: c'è una struttura come un albero coinvolto? (Come sopra). Se è così, probabilmente puoi attraversarlo.

score 1 · Answer 2

Il modo migliore per sapere quando la ricorsione è appropriata è l'esperienza. Usalo e otterrai un tocco in più quando è appropriato. Prova anche ad imparare una lingua funzionale, non ho capito quanto possa essere utile la ricorsione finché non ho iniziato ad imparare F #

score 0 · Answer 3

When studying a problem, is there any technique or trick to see that a recursion based approach can be used or not?

Sì, certo, anche se non lo definirei un trucco. Dovrebbe essere una conoscenza di base che nei linguaggi imperativi c'è davvero solo un tipo di ciclo, il ciclo while (ogni altro ciclo è semplicemente zucchero sintattico). Ma un ciclo while corrisponde direttamente a un pattern ricorsivo che le ho dato in una notazione simile a haskell:

loop False action = return ()
loop True  action = action >> loop nextCondition nextAction
   where
       nextCondition = .....
       nextAction    = .....

Quindi, la conclusione è: un approccio basato sulla ricorsione può essere usato per il problema ogni . Piaccia o no.