Ricorsione in Algoritmo di merge sort. Com'è ovvio usare questo tipo di ricorsione?

Il MergeSort ricorsivo è un algoritmo "divide et impera". Il codice che hai fornito nell'esempio fondamentalmente lo fa (in inglese semplice):

1. Trova il punto centrale
2. Ordina la metà sinistra,
3. Ordina la metà destra.
4. Unisci le due metà di nuovo insieme.

La chiave per capire come funziona in modo ricorsivo è che, quando si ordina la metà sinistra, la divide in due parti, proprio come ha fatto con le prime due metà, e così via. Visivamente, puoi considerarlo come una struttura ad albero, con la radice in alto e rami progressivamente più piccoli che si estendono verso il basso.

Questo processo di divisione continua finché il codice non incontra una condizione di uscita. Una volta che si incontra questa condizione di uscita, il codice inizia a ritornare sui rami dell'albero, unendo i rami insieme quando ogni chiamata ricorsiva ritorna all'albero.

Le funzioni ricorsive hanno sempre tre elementi in comune (di solito in questo ordine):

1. La condizione di uscita,
2. La chiamata ricorsiva e
3. Il lavoro svolto in questa ricorsione.

Questo è una rappresentazione pseudocodice migliore da Wikipedia . Verifica se riesci a individuare tre elementi :

function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the even and odd-indexed elements.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i is odd then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

La funzione merge unisce gli elenchi mentre si fa risalire la struttura delle chiamate:

function merge(left, right)
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Il blog di Penjee ha alcune animazioni eccellenti che ti aiutano a visualizzare questo processo. Ecco uno che disegna effettivamente un albero come quello che ho menzionato:

Il principio generale della ricorsione è quello di risolvere un problema ipotizzando che un problema più piccolo possa essere risolto, e tenendo conto della differenza tra il problema più piccolo e quello che viene attualmente chiesto di risolvere.

Molti algoritmi ricorsivi, ad es. fattoriale ricorsivo, assume un problema più piccolo per 1 e poi, data la risposta, risolve il delta tra quella (più piccola per una) risposta e la risposta richiesta, ad es. moltiplicando la risposta del problema più piccolo di N.

Nel caso della tua domanda, l'approccio è quello di risolvere non solo uno ma due problemi minori e combinare la risposta usando l'unione. I problemi minori sono suddivisioni del problema più grande in m , che è la metà dell'intervallo che è stato chiesto di risolvere.

A proposito, ci sono molti modi diversi in cui unire l'ordinamento è codificato. In parte dipende dal fatto che la tua lingua supporti efficientemente fette di array (o meno).

Se lo fa, l'ordinamento di unione viene in genere chiesto di ordinare un array dato ad ogni invocazione, dove l'array da ordinare è in realtà un sottoinsieme di un array più grande, ma una volta passato come argomento, viene visto passare da 0 a alcuni .length.

Se la lingua non consente fette, come potrebbe essere il caso nella tua domanda, allora l'ordinamento di fusione viene diretto per ordinare un sotto intervallo identificato esplicitamente dell'array (passando l'inizio aggiuntivo ( l ) e fine ( r ) parametri) invece di trasformare la porzione in un altro array (slice) e passare solo quella.

In ogni caso dovrebbe essere relativamente facile vedere che m è scelto a metà circa tra l e r . Quindi, la prima delle due chiamate ricorsive richiede di ordinare subrange l a m , e il secondo, il subrange da m+1 a r . Una volta uniti, questo esegue il tipo richiesto dell'intero l a r subrange richiesto.

La chiamata iniziale avrà l come 0 e r come lunghezza intera, quindi alla prima chiamata viene chiesto di ordinare l'intero array e, a sua volta, chiede ai suoi assistenti ricorsivi di ordinare circa la metà dell'array. A loro volta suddividono anche la porzione dell'array a cui sono chiesti di dividere in circa la metà ... Alla fine, l'intero intervallo dell'array originale viene ordinato e unito.

Molti algoritmi ricorsivi usano più di una chiamata (auto) ricorsiva. Ad esempio, gli attraversamenti di alberi ricorsivi funzionano in modo simile: un attraversamento di ordine postale visita il nodo stesso per ultimo dopo essere chiamato ricorsivamente a sinistra ea destra. Potresti vedere la suddivisione in due problemi più piccoli più facilmente con la ricorsione di un attraversamento di alberi perché c'è molto meno lavoro da fare per identificare il problema più piccolo da risolvere prima (c'è solo destra e sinistra).

Ma l'ordinamento di fusione fa la stessa cosa: per ogni intervallo che viene chiesto di ordinare, prima (usando l'invocazione ricorsiva) ordina la metà sinistra, poi la metà destra, quindi si unisce. Deve identificare le metà usando un po 'di aritmetica, che la differenzia dall'altra traversata ad albero con motivi simili.

Una variante dell'ordinamento di unione potrebbe suddividere l'array in tre sezioni, ordinandole ciascuna (in modo ricorsivo, ovviamente) e poi unendole. La parte di unione richiederebbe un parametro aggiuntivo (per la terza parte scelta, ad esempio merge(array,l,m,n,r); ).

Psicologicamente, la ricorsione in programmazione è simile a "prova per induzione" in matematica. (Nel caso non si abbia familiarità con la dimostrazione per induzione, consiste nel provare "Se P è vero per n = m allora è vero per n = m + 1", osservando che P è vero per n = 0 [o n = 1, se preferisci], e deducendo che P è vero per tutto il n).

Con l'induzione matematica, diverse persone pensano in modi diversi. Ad esempio, verificando prima n piccoli, o prendendo il quadro generale e lavorando verso il basso.

Per la tua ricorsione, la guardo in questo modo:

1. Supponiamo che il "inner" mergeSort funzioni.

2. Leggi il codice e verifica che la funzione mergeSort funzioni se le chiamate interne a mergeSort funzionano. Questo è equivalente al passo induttivo in matematica.

3. Convinciti che il mio ragionamento non è circolare trovando qualcosa diverso sul "inner" mergeSort . In questo caso - che quelli "interni" sono sempre più piccoli.

4. Si noti che esiste un caso "più interno", "n = 0". Nel tuo esempio, è quando 0 elementi rimangono da ordinare, penso (o 1: puoi controllare).

5. La prova induttiva è quindi completa. Potresti dire che il ragionamento non è circolare, ma spirale.

6. La ricorsione è sempre una cattiva pratica nell'ingegneria del software perché si sta utilizzando una quantità sconosciuta e incontrollata di una risorsa (lo stack) di dimensioni finite e la cui dimensione è determinata dagli ingegneri che incrociano le dita e fanno speranze indovina. Quindi c'è ancora una cosa da controllare, e questa è la profondità della ricorsione. Ed è qui che entra in gioco la scelta del "punto medio" m . L'algoritmo funzionerà in teoria con qualsiasi valore di m , ma la ragione per cui il valore a metà strada usato qui è che rende il successivo interno mergeSort metà della dimensione. L'algoritmo è ancora una cattiva ingegneria in generale, ma per un piccolo numero di valori da ordinare, la profondità della ricorsione è piccola. Ad esempio, se ci si limita a ordinare non più di 2 ^ 64 numeri interi, la profondità massima di ricorsione è solo 64, che è tollerabile.

I was hoping that someone could provide me with insight as to how I should think about these two recursion calls, and how its obvious it had to be this way.

Ci sono fondamentalmente due cose che devi padroneggiare:

1. Devi essere in grado di riconoscere che un problema è potenzialmente suscettibile a una soluzione ricorsiva.

2. Devi essere in grado di formulare la soluzione ricorsiva.

Non penso che ci sia qualche formula magica speciale per imparare uno di questi, eccetto per leggere libri su algoritmi (specialmente quelli scritti da esperti di programmazione funzionale) ... e pratica. Con abbastanza pratica, diventa più semplice individuare l'opportunità per la ricorsione e codificarla.

Non essere scoraggiato dal fatto che non puoi (ad esempio) ideare un quicksort o un algoritmo di un fusore da zero senza indizi. Non dimenticare che le persone che hanno ideato per la prima volta queste cose erano persone davvero intelligenti. Le persone normali come te e me comprendono questi algoritmi / questo modo di pensare perché leggiamo o ci è stato insegnato quicksort, ecc. Quindi applichiamo la stessa conoscenza ad altri problemi simili.

Solo per fornire una risposta molto breve. Questo funziona per la maggior parte dei tipi di funzioni ricorsive.

Non hai bisogno di passare attraverso la ricorsione è la tua testa. Hai solo bisogno di scrivere la funzione per il parametro dato, ad esempio un elenco di elementi, pur assumendo che la funzione funzioni già se la chiami con un elenco di elementi più piccolo.

Analogamente nell'esempio di mergeSort, quando scrivi o guardi la funzione con i parametri l e r , supponi che la funzione funzioni già per una differenza minore tra l e r .

Le dimensioni di un elenco finito non possono essere ridotte all'infinito, né lo scarto tra l e r , quindi non devi preoccuparti che la ricorsione avvenga per sempre.