Ecco un esempio: percorrere l'albero dei directory su di un disco, usando le funzioni delle API di Windows FindFirstFile/FindNextFile/FindClose, ma, naturalmente, la struttura della funzione sarebbe identica per qualsiasi altro compito in cui bisogna percorrere (ad esempio per costruirne un modello in memoria) un albero appoggiandosi su funzioni analoghe ("trova il primo figlio del nodo corrente", "trova il prossimo nodo", "Ok, con l'esame dei figli di questo nodo ho finito"). Per concretezza, lo scopo della funzione di esempio è il calcolo dell'occupazione complessiva di disco da parte dell'intero albero, in termini di numero di byte; come albero interessa quello che inizia dal directory corrente, e la specifica del prototipo della funzione è:

 long getOccupiedBytes(void);

Partiamo, anzitutto, dalla versione basata su di una funzione recursiva, basata sull'idea: il numero di byte occupati da un sottoalbero è la sommatoria dei byte dei file che contiene il suo directory-radice, più i byte occupati da ciascun sottoalbero la cui radice è un sottodirectory della radice -- recursivamente. Usiamo inoltre una funzione ausiliaria "bool isDummy(const char* directoryName)" che ritorna true per "." e "..", tipici directory-dummy nei quali non si vuole entrare, banalmente, ad esempio:

 bool isDummy(const char* directoryName) {
  if(0==strcmp(directoryName,".")) return true;
  if(0==strcmp(directoryName,"..")) return true;
  return false;
 }
Infine, ignoriamo per semplicita` il fatto che "un file di 3 byte" non occupa 3 byte, bensi` un intero cluster (solo perchè qui interessa mostrare la struttura...!), come pure i file più grandi di 4 gigabyte, la diagnostica di errori, ecc ecc.

long getOccupiedBytes(void)
{
 long result=0;
 WIN32_FIND_DATA wfd;
 HANDLE hFind = FindFirstFile("*.*",&wfd);

 for(;;) {
  result += wfd.nFileSizeLow;
  if(wfd&FILE_ATTRIBUTE_DIRECTORY) {
   if(!isDummy(wfd.cFileName)) {
    SetCurrentDirectory(wfd.cFileName);
    // la chiamata recursiva:
    result += getOccupiedBytes();
    SetCurrentDirectory("..");
   }
  }
  if(!FindNextFile(hFind,&wfd)) {
   FindClose(hFind);
   return result;
  }
 }
}

Per rimuovere la singola chiamata recursiva, bisogna trovare un altro modo, alternativo alla recursione, di dire, in quel punto: "salva i dati che non vanno alterati, e ricomincia l'elaborazione dall'inizio"; e, dove ora abbiamo il "return, bisogna invece avere un altro modo, compmementare, di dire "recupera i dati che in precedenza erano stati salvati, e riprendi l'esecuzione dal punto del precedente ''ricomincia''" (verificando, naturalmente, se _esistono_ ancora "dati in precedenza salvati"; se no, occorre fare return dall'intera funzione).

Siamo qui molto fortunati, dal punto di vista della semplicità di rimuovere la recursione, perchè c'è un singolo punto di chiamata recursiva, e un singolo punto di ritorno; inoltre, la funzione è priva di argomenti (una bella semplificazione!),E, altra cosa che ci facilita molto, c'è UN SOLO dato da salvare: la HANDLE hFind. Infatti, "result" è usato in modo tale che basta continuare a sommargli i dati, mentre wfd è un "buffer" sovrascritto da ogni chiamata a FindNextFile -- non mantiene dati "importanti" da un ciclo all'altro.

long getOccupiedBytes(void)
{
 long result=0;
 WIN32_FIND_DATA wfd;
 std::vector<HANDLE> savestack;

 for(;;) {
  HANDLE hFind = FindFirstFile("*.*",&wfd);
  for(;;) {
   result += wfd.nFileSizeLow;
   if(wfd&FILE_ATTRIBUTE_DIRECTORY) {
    if(!isDummy(wfd.cFileName)) {
     SetCurrentDirectory(wfd.cFileName);
     savestack.push_back(hFind);
     break; // dal loop interno torna all'esterno
    }
   }
   while(!FindNextFile(hFind,&wfd)) {
    FindClose(hFind);
    SetCurrentDirectory("..");
    if(savestack.empty())
     return result;
    hFind = savestack.back();
    savestack.pop_back();
   }
  }
 }
}

La cosa quasi miracolosa è che qui siamo riusciti a rimuovere la recursione senza nessun esplicito goto...! Di solito (con più di un punto di chiamata recursiva, e/o più di un punto di ritorno), non se ne potrà fare a meno.

Certo, la "amplificazione di complessità" del flusso di controllo della funzione resta pur sempre paurosa, con tre loop annidati: il for(;;) esterno è dove si inizia l'analisi di ogni sub-directory, quello interno il "normale" loop sui file (e sub-dir) di ogni directory, e il while al suo interno (mutazione dell'if della originale routine recursiva) forse il più "trucchistico" di tutti, poichè serve a diagnosticare la fine di un directory e anche a "riprendere" la "normale" analisi del suo directory-padre. Ma forse, a pensarci bene, la cosa più strana è il break del for(;;) interno, che non è la FINE di una qualche sequenza di operazioni, bensi` l'INIZIO di una ricerca "annidata" (infatti, uscendo dal for interno, il controllo passa al for esterno, che riparte con FindFirstFIle).

Normalmente, rimuovere la recursione richiede molte più complicazioni, e, in particolare, rende inevitabile l'uso di espliciti goto (un'alternativa equivalente ad essi è un modello con esplicita "macchina a stati finiti" -- un for(;;) con dentro uno switch() -- che qui lasciamo come esercizio per il lettore).

Le prestazioni della versione non recursiva sono indistinguibili, in termini di misurazioni, da quelle della versione recursiva. Nondimeno, in teoria, un vantaggio ci dovrebbe essere (se le recursioni sono annidate MOLTO profondamente), poichè, nella versione non-recursiva, possiamo (e, in effetti, DOBBIAMO) decidere esplicitamente COSA salvare (qui, la sola HANDLE hFind), mentre una chiamata recursiva "salva tutto" quello che vive nello stack, sia le nostre esplicite variabili, sia dei "dati impliciti" gestiti dal compilatore (frame pointer, instruction pointer alla chiamata per poter eseguire il return "giusto"). In situazioni di memoria estremamente scarsa, e anche di recursioni estremamente profonde, questa unica caratteristica positiva del "recursion removal" può essere proprio quella che "ci salva la ghirba".

Come per tutte le tecniche di ottimizzazione, vale, naturalmente, il motto "impara l'arte, e mettila da parte"; l'ottimizzazione prematura è causa di molti mali (il codice ottimizzato è più difficile da capire, manutenere, modificare, eccetera). In generale sarà più semplice, più produttivo, ed equivalente in termini di prestazioni, scrivere il programma usando dapprima la recursione; se si evidenziano problemi di prestazioni (memoria), allora si può rimboccarsi le maniche e rimuovere la recursione -- lasciando, come commento, la chiara e nitida versione recursiva, ma passando a quella, più complessa e fragile, non-recursiva, per risparmiare qualche prezioso byte, o qualche prezioso ciclo di CPU.