Ricorsione - è "divide and conquer" o "riuso del codice"

• what are the "problem patterns" that call for the solution of recursion

Non direi che esiste una cosa del genere come un modello di problema per l'uso della ricorsione. Ogni funzione che può essere implementata con la ricorsione può anche essere implementata in modo iterativo, spesso premendo e scoppiando una pila.

È una questione di espressione e anche di prestazioni. Gli algoritmi iterativi spesso hanno prestazioni migliori e sono più facili da ottimizzare. Tuttavia, gli algoritmi ricorsivi beneficiano di un'espressione più chiara e quindi sono spesso più facili da leggere, comprendere e implementare.

Alcune cose anche non possono essere espresse senza ricorsione, liste infinite per esempio. I cosiddetti linguaggi funzionali fanno molto affidamento sulla ricorsione, in quanto è il loro modo naturale di espressione. Il detto è: "La programmazione ricorsiva è una programmazione funzionale fatta bene".

• is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

Non lo definirei un modello di progettazione. È una questione di espressione. A volte un'espressione ricorsiva è semplicemente più potente e più espressiva e quindi porta a un codice migliore e più pulito.

• can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Qualunque cosa abbia bisogno di attraversare alberi sarà espressa correttamente da un algoritmo ricorsivo.

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

Nessuno dei due. Dividi e amp; conquista usa ricorsione. Ma la ricorsione non è necessariamente dividere & conquistare poiché quest'ultimo significa dividere un problema in due (o più) parti e risolverne ognuna simmetricamente. In ricorsione, non lo fai.

Il riutilizzo del codice non è completamente correlato e un modello di progettazione entra in gioco a un livello molto più alto. Ad esempio, anche dividi & conquistare (anche uno schema di livello superiore rispetto alla ricorsione) non è ancora considerato un modello di progettazione - piuttosto, è un modello algoritmico .

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Attraversamento dell'albero. O più generalmente attraversamento grafico. Questo include in particolare il passaggio di una struttura di cartelle.

E ovviamente tutto ciò che usa divide & conquistare o programmazione dinamica poiché entrambi sono espressi naturalmente in termini di ricorsione.

what are the "problem patterns" that call for the solution of recursion

Derivato dall'auto-somiglianza dei frattali, direi che l'auto-uguaglianza o l'auto-identità (o comunque è chiamata) è un tipico modello di problema per la ricorsione. Cioè un problema può essere suddiviso in sotto-problemi che hanno la stessa struttura del problema principale.

Nel traversal dell'albero menzionato, ogni sotto-albero è un albero completo in sé stesso, proprio come l'albero principale, e l'albero principale può essere un sotto-albero all'interno di un altro albero.

Quindi immagino che il tuo collega abbia scoperto le proprietà di auto-eguaglianza del tuo problema di indicizzazione. Oppure è andato al contrario e ha trasformato il problema in una rappresentazione egualitaria.

Bene, la ricorsione può essere facilmente compresa se si tenta di trasformare i cicli imperativi in funzioni funzionali. Ad ogni modo, proviamo a dare risposte a tutte le domande:

what are the "problem patterns" that call for the solution of recursion

Se hai una struttura ad albero o un algoritmo avrai bisogno di una ricorsione. Se il tuo codice imperativo si occupa di uno stack, avrai bisogno di una ricorsione. Se un determinato passaggio nell'algoritmo dipende da passaggi precedenti (loop di pensiero), è necessario ricorrere. Bisogno qui deve essere interpretato come può usare.

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

Nessuno. Dividi e conquista utilizza la ricorsione, ma può essere implementato con pile. Il riutilizzo del codice si riferisce a qualcos'altro. I modelli di progettazione sono più complicati della semplice ricorsione.

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Analisi e tutto ciò che riguarda le strutture ad albero. Anche strutture ad albero implicite.

Se c'è un modo per semplificarlo in modo che sia facile, quello può essere l'indizio che la ricorsione potrebbe funzionare. Potresti prendere l'ordinamento e cercare esempi dove esistono soluzioni ricorsive come Merge Sort e Ricerca binaria rispettivamente.

Qualcosa da tenere a mente è come alcuni problemi possono essere risolti male con la ricorsione come un fattoriale.

Per quanto riguarda un esempio del mondo reale in cui utilizzerei la ricorsione, la ricerca di un libro fuori dallo scaffale di un libro può essere eseguita abbastanza facilmente in modo ricorsivo. Io guardo il libro e se non è quello che voglio, passerò a quello successivo. Mi fermo quando trovo il libro o prendo la fine della riga. Il loop su come controllare un libro e passare a quello successivo potrebbe essere fatto in modo ricorsivo. Forse questo è troppo reale per un esempio.

what are the "problem patterns" that call for the solution of recursion

In termini molto generali, la ricorsione è richiesta quando si risolve un problema in cui f (x) = f (g (x)) . A meno che tu non stia bene con la ricorsione infinita, g (x) non dovrebbe valutare x .

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

Nessuna delle precedenti. È solo un modo per ripetere la stessa cosa ripetutamente, a volte in base a variazioni sull'input. Il concetto è stato molto più lungo di schemi di progettazione, riutilizzo del codice o persino computer, per questo.

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

I fattoriali, la sequenza di Fibonacci, l'attraversamento degli alberi e molti altri problemi possono essere risolti con il recustion. La ricorsione nel senso di una funzione che chiama se stessa non è necessariamente il modo migliore per implementare questo tipo di cose; ci sono altri modi per ottenere lo stesso effetto (ad es. uno stack e un loop) che potrebbe essere più desiderabile.

Quando scrivi un algoritmo ricorsivo, di solito traduci una definizione ricorsiva del problema nel codice. Quindi non hai nemmeno bisogno di sapere come verrà eseguito.

È ciò che accade nella programmazione funzionale. In effetti, specifica cosa (definizione) piuttosto che come . In altre parole, definisci la base e poi definisci il tuo problema nel termine di un sotto-problema.

Ad esempio, considera l'algoritmo Factorial

• Definisci la base: Fattoriale (1) = 1;
• Definisci Fattoriale n: Fattoriale (n) = n * Fattoriale (n-1);

Quindi quando incontri un problema, dovresti pensare se puoi definirlo ricorsivamente o meno, se puoi definirlo in modo ricorsivo, lo hai quasi risolto.

Tuttavia, qualsiasi funzione ricorsiva non dovrebbe essere una definizione ricorsiva. È possibile definire la base e collegare (definire) la soluzione del problema principale alla soluzione (definizione) dei sotto-problemi. Ma per questa relazione potresti aver bisogno di una procedura.

Un esempio è MergeSort in cui merge potrebbe essere una procedura imperativa per mettere in relazione la definizione o la soluzione di ordinare l'intero array al tipo di sotto-array.