Si l'algoritmo funziona bene... cmq io l'avrei fatto in un altro modo + semplice e con meno variabili

codice:
template <class T,class N>
int Bin_tree<T,N>::maxProfondita(Bin_tree<T,N>::Nodo n)
{
    /* se è vuoto lui stesso allora ritorno 0 */
    if (empty())
        return 0;
    /* se non ha nodi però questo nodo non è vuoto, ritorno 1 */
    if (sx_empty(n) && dx_empty(n))
        return 1;
    /* se questo nodo non è nullo e ha un nodo a sinistra ritorno 1+calcolo di
        profondita di sinistra */
    if (!sx_empty(n) && dx_empty(n))
        return 1+maxProfondita(sx(n));

    /* se questo nodo non è nullo e ha un nodo a destra ritorno 1+calcolo di
        profondita di destra */
    if (sx_empty(n) && !dx_empty(n))
        return 1+maxProfondita(dx(n));
    /* se questo nodo non è nullo e ha un nodo a sinistra ed uno a destra
        ritorno 1+calcolo di profondita di sinistra + calcolo di profondità di destra */
    if (!sx_empty(n) && !dx_empty(n))
        return 1+maxProfondita(dx(n))+maxProfondita(sx(n));
}
Questo non l'ho provato ma dovrebbe funzionare.
Ovviamente posta la condizione che se un nodo parent è vuoto allora non possa avere altri nodi child.
Cmq per le ricorsioni è un problema. E' un metodo che usano in pochi intanto perchè si rischia lo stack overflow in caso di ricorsioni lunghe (richiamare molte volte la stessa funzione, rischia di far riempire lo stack), e poi perchè è un algoritmo + difficile rispetto magari ad un normale ciclo.
Dall'altra c'è un miglioramento della leggibilità.

Per imparare devi solo applicarli, magari con funzioni facili tipo somma, differenza, calcolo delle potenze ecc...