È bene capire almeno come funziona la ricorsione, perché alcuni algoritmi sono naturalmente ricorsivi e quindi molto più facili da esprimere usando la ricorsione.
Inoltre, gli algoritmi ricorsivi (o le implementazioni) non sono intrinsecamente più lenti di quelli iterativi. In effetti, ogni algoritmo ricorsivo può essere implementato da un'equivalente implementazione iterativa al costo di dover tenere traccia di alcuni valori intermedi / temporanei, dove la versione ricorsiva tiene automaticamente traccia di quelli nello stack delle chiamate di funzioni.
Un esempio di algoritmo ricorsivo è se si desidera applicare un'operazione a tutti i nodi di un albero. L'implementazione più naturale qui è quella di avere una funzione che esegue l'operazione su un nodo e si chiama in modo ricorsivo per ciascuno dei figli del nodo.
Per alcuni algoritmi, come il calcolo di una sequenza di Fibonacci, la ricorsione sembra naturale, ma un'implementazione ingenua sarà molto più lenta di un'implementazione iterativa, perché la versione ricorsiva continua a ripetere lo stesso lavoro più e più volte. Questo significa che per quei particolari algoritmi, la ricorsione potrebbe non essere la scelta migliore, o che è necessario utilizzare alcune tecniche per ricordare valori intermedi che potrebbero essere necessari di nuovo altrove nell'algoritmo.
Per altri algoritmi, in particolare quelli che usano tattiche divide e conquista, scoprirai che hai bisogno di uno stack per tenere traccia di alcune cose nella soluzione iterativa. In questi casi, una versione ricorsiva è molto più pulita, perché la gestione dello stack diventa implicita.