Su questo argomento ho sbattuto la testa anch'io per un bel po' di tempo qualche mese fa prima di riuscire a capirlo. Vediamo se riesco a darti una mano. Nell'esempio da te postato devi immaginare una sequenza di funzioni che operano su un numero via via minore fino a 0. Immagina che l'input in questione sia 2 (giusto per prendere un numero ragionevolmente piccolo ma che spero sia sufficiente a capire) e osserva cosa fa la funzione.

1: la prima chiamata è fact (2). 2 non è zero quindi salta l'if e tenta di ritornare n* fact (n-1). però non sa quanto vale fact (n-1) e quindi va a calcolarlo chiamando fact (1) (nota che le variabili utilizzate nella prima chiamata rimangono salvate in memoria ad aspettare che la fact (1) faccia il suo sporco lavoro).

2: siamo scesi in fact (1) mentre fact (2) attende un risultato. 1 è diverso da 0 quindi ancora tenta di ritornare n* fact (n-1) ma deve calcolarlo e chiama la funzione fact (0) (anche qui fact (1) resta paziente in attesa).

3: riceve 0 e quindi la funzione passa 1 a quella che la precede e termina.

4: Siamo tornati in fact (1) che a questo punto è in grado di ritornare n* fact (n-1) che fa 1 e fatto ciò termina e libera la memoria che ha utilizzato.

5: fact (2) è in grado di ritornare a sua volta n* fact (n-1) che fa 2 e termina.

Tenendo a mente il discorso fatto sopra ti faccio ora un esempio con la visita inorder di un albero binario visto che te li hanno fatti fare. Consideriamo per esempio il seguente albero: (metto come codice solo per rendere più chiara la forma)
codice:
    6
   / \
  4   9
 / \
2   8
e consideriamo la seguente funzione che è abbastanza famosa o comunque molto utilizzata:
codice:
void inOrder (tree *node) {  /*node è un puntatore a struct tree*/
    if (node== NULL) return;
    inorder (node-> left); /* left e right sono puntatori al figlio sinistro e destro */
    visit (node); /* visit esegue una qualsiasi operazione sul nodo, ma a noi non interessa */
    inorder (node-> right);
}
- La prima chiamata riceve in input il puntatore al nodo 6. Il puntatore non è nullo quindi chiama inOrder () relativa al nodo 4.

- Ancora non è nullo quindi chiama inOrder relativa al nodo 2.

- Il puntatore a 2 non è nullo e chiama inOrder del figlio sinistro di 2.

- Il figlio sinistro di due non c'è quindi il suo puntatore è nullo. Ritorna.

- A questo punto ritorna sul nodo 2 e lo visita.

- Scende al figlio destro di 2 che non c'è e quindi ritorna a 2.

- Torna a 4 e lo visita.

- Scende sul figlio destro di 4 e tenta di visitarne il figlio sinistro, ma 8 non ce l'ha e quindi visita 8.

- Tenta di visitare il figlio destro di 8, ma 8 non ce l'ha e quindi ritorna a 4 e successivamente a 6 e visita 6.

- A questo punto scende al figlio destro di 6 e tenta di visitarne il figlio sinistro che non c'è e quindi visita 9.

- Tenta ancora di visitare il figlio destro di 9 ma non c'è e quindi torna a 9 e poi a 6 e infine termina.

Riassumendo, l'ordine di visita è 2 4 8 6 9.
Inoltre vorrei precisare che una funzione ricorsiva è una funzione che chiama una copia di sè stessa e non sè stessa perchè lei e la sua copia operano su input differenti e comunque il loro rapporto si limita allo scambio di informazioni. Differenza sottile ma comunque differenza.
Se ho sbagliato qualcosa correggetemi e non crocifiggetemi , comunque spero di essere stato utile

(fonti: corso di algoritmi e programmazione al polito)