La funzione è sbagliata - o l'hai copiata sbagliata; dovrebbe essere:
codice:
void delete_list(link head) {
    if(head_of_list->next)// testa della lista
    {
        delete_list(head_of_list->next);
        delete_node(head_of_list);
    }
}
con delete_node all'interno dell'if, non fuori, altrimenti ottieni un segmentation fault in delete_node arrivato in fondo alla lista.

Ciò detto, il funzionamento è relativamente semplice una volta entrati nella mentalità ricorsiva: cosa devo fare per eliminare una lista? Prima elimino gli elementi che seguono, quindi dealloco l'elemento corrente, ed è esattamente quello che fa la funzione: se non siamo ancora in fondo alla lista, richiama ricorsivamente sé stessa sul prossimo elemento. A questo punto, quando la delete_list è ritornata, sa che tutti gli elementi dopo sono già stati eliminati, e può procedere a deallocare il nodo corrente usando la delete_node.
Il "caso base" è quando la delete_list riceve NULL - in tal caso, non c'è niente da fare e si limita a ritornare.

P.S.: qui come nell'altro thread, ho proceduto a sistemare tra tag [CODE] ... [/CODE] il codice e ad indentarlo correttamente, in futuro ricordatene.