Короче, есть несколько канонiчных (я правильно написал это слово? 😊) задач на рекурсию, большинство из них связано с обработкой деревьев:
1. Разбор синтаксического выражения в AST.
2. Преобразование AST, например, упрощение выражения.
3. Операции над списками в ФП стиле, insert, delete, map, fold, length, transpose, find и др.
4. Merge sort тоже в ФП стиле.
5. Реализация красно-чёрного дерева в ФП или в императивном стиле (и там, и там требуется рекурсия, но мутация вынуждает перекрашивать ноды по-разному чтобы сохранить инвариант)
6. Реализация двоичного дерева поиска в ФП.
7. Инвертирование двоичного дерева поиска (делается буквально в 3 строчки, не знаю, почему у тех, кто собеседуется в гугл так пылает).
8. Решение игры про Ханойские Башни.
9. Решение судоку.
Для примера можешь глянуть мои упражнения на преобразование арифметических выражений в обратную польскую запись и вычисление значений.
https://github.com/nlinker/playground/tree/master/rust/shunting-yard