Scrittura di funzioni ricorsive

Sei fortunato! Lì (ordinamento) è!

Quello che spesso si vuole fare è identificare i casi 2/3:

1. Il caso base
2. Il caso ricorsivo
3. Il caso di uscita (a volte facoltativo)

Cioè:

1. Che cosa vuoi fare
2. Dove è necessario continuare
3. Al termine

Pensa ad un esempio (DFS su un albero di ricerca binario):

bool DFS(Node currentNode, T searchValue)
{
    // base case
    if (currentNode.Value == searchValue) 
        return true;

    // recursive case and exit case
    if (curentNode.Left != null && DFS(currentNode.Left, searchValue)) 
        return true;

    // recursive case and exit case
    if (curentNode.Right != null && DFS(currentNode.Right, searchValue))
        return true;

    return false;
}

Quindi, ecco:

1. Caso di base: se abbiamo trovato il nostro valore
2. Casi ricorsivi: eseguire DFS nei nodi figlio
3. Caso di uscita: restituisce true se DFS sui nodi figlio ha trovato il valore

Quindi ora pensa al traversal in ordine dello stesso albero:

1. Caso di base: stampa il nodo
2. Caso ricorsivo:
   • visita il figlio sinistro
   • visita il figlio giusto
3. Exit case (s): esiste il nodo?

Nel caso di attraversamenti interni sembra che:

void InOrder (Node currentNode)
{
    // 3
    if (currentNode == null)
        return;

    // 2
    InOrder(currentNode.Left);
    // 1
    print(currentNode.Value);
    // 2
    InOrder(currentNode.Right);
}

Quasi tutte le funzioni ricorsive avranno questi elementi. Identificarli e metterli nel giusto ordine è la chiave.

C'è qualche "trucco" per riuscire a creare un algoritmo / scrivere psuedocode per funzioni ricorsive?

Assolutamente! Quando scrivi una funzione ricorsiva, stai descrivendo esplicitamente l'induction che stai preformando sul dato datastructure. Pertanto, quando scrivi la tua funzione, il "trucco" è duplice:

• Copri tutte le diverse forme rappresentate dalla tua infrastruttura (IE, hai casi per i leaf AND di un albero, o le celle AND empty-lists in un elenco collegato, o numeri positivi AND zero se stai ricorrendo ai numeri.
• Quando hai a che fare con il caso contenitore (cella in un elenco, nodo in un albero), riduci il problema in sottoproblemi e trova un modo per combinarli, se necessario.

Ad esempio, ecco una funzione ricorsiva per contare tutti i nodi in un albero:

def TreeCount(Tree):
    if Tree.isLeaf: # we can't go down any further
        return 1 
    else: # break the problem into sub-problems we can solve with this function
        return 1 + TreeCount(Tree.left) + TreeCount(Tree.right) 

Come puoi vedere, ho diviso la funzione sul tipo di albero che stavamo guardando (Leaf vs Node) e nel caso in cui avessi a che fare con un nodo, l'ho elaborato in termini di ricorsioni sui suoi sottoalberi.