Nell'implementazione di una funzione ricorsiva, in generale ci sono 3 situazioni da prendere in considerazione:
1) fase di inizializzazione
2) base della ricorsione
3) passo ricorsivo.
Una funzione ricorsiva che processa una struttura dati e', ovviamente, facilmente implementabile quando la struttura e' definibile in modo ricorsivo.
Ed anche una struttura dati definita in modo ricorsivo, deve prendere in considerazione almeno 2 situazioni distinte:
1) la base della ricorsione
2) la definizione ricorsiva.
Ora il tutto si risolve capendo come funzionano questi 2/3 passi.
Un modo per capire puntualmente come fare il tutto e' quello di ricordarsi l'enunciato del principio di induzione, un super classico esempio (praticamente la base) di definizione ricorsiva:
P(0) e' vera [base del principio di induzione]
se P(n) e' vero implica che P(n+1) e' vero, allora P(x) e' vero per ogni x intero >= 0
[passo ricorsivo in avanti: n -> n+1]
Qui' c'e' un trucco: invece di andare in avanti (n -> n+1) si puo' riformulare la definizione all'indietro:
( n-1 -> n)
se P(n-1) e' vero implica che P(n) e' vero, allora P(x) e' vero per ogni x intero >= 0
[passo ricorsivo all'indietro n-1 -> n]
Ora, devi per prima cosa definire la lista in modo ricorsivo. Abbastanza ragionevolmente n puo' essere identificato come la lunghezza della lista. Quindi
P(0) che cosa e' una lista di lunghezza 0?
P(n) -> P(n+1) come e' fatta una lista di lunghezza n+1 quando si conosce la struttura di una lista di lunghezza n?
OPPURE
P(n-1) -> P(n) come e' fatta una lista di lunghezza n quando si conosce la struttura di una lista di lunghezza n-1?
Una volta capito questo, l'algoritmo ricorsivo per la ricerca del massimo e' semplicemente una variante dell'applicazione del principio di induzione.