Niedawno widziałem w kilku różnych miejscach komentarze na wzór: „Nauczyłem się rekursji w szkole, ale nigdy jej nie użyłem ani nie odczuwałem jej potrzeby”. (Rekursja wydaje się być popularnym przykładem „uczenia się książki” wśród pewnej grupy programistów).

Cóż, prawdą jest, że w językach imperatywnych, takich jak Java i Ruby [1], generalnie używamy iteracji i unikamy rekursji, częściowo z powodu ryzyka przepełnienia stosu, a częściowo dlatego, że jest to styl, do którego jest używany większość programistów w tych językach .

Teraz wiem, że ściśle mówiąc, nie ma „koniecznych” zastosowań rekursji w takich językach: zawsze można jakoś zastąpić rekursję iteracją, bez względu na to, jak skomplikowane rzeczy się pojawią. „Konieczne” tutaj mówię o następujących kwestiach:

Czy możesz wymyślić jakieś konkretne przykłady kodu w takich językach, w których rekursja była o wiele lepsza niż iteracja (ze względu na jasność, wydajność lub w inny sposób), że mimo wszystko używałeś rekurencji, a konwersja na iterację byłaby dużą stratą?

Rekurencyjnie chodzące drzewa zostały kilkakrotnie wspomniane w odpowiedziach: jakie było dokładnie to, czego używałeś, aby uczynić rekursję lepszym niż użycie iteratora zdefiniowanego w bibliotece, gdyby było dostępne?

[1]: Tak, wiem, że są to także języki zorientowane obiektowo. Nie ma to jednak bezpośredniego związku z tym pytaniem.