Рекурсия становится понятной, если разбирать её на связном списке

Автор честно пишет, что структуры данных на C++ дались ему тяжелее всего за год, и дольше прочего не давалась именно связка связных списков с рекурсией.

Половину сложности объясняет разница с массивом. В массиве всё лежит рядом в памяти, и элемент берётся по индексу. В связном списке каждый узел хранит значение и указатель на следующий: чтобы добраться до пятого, надо пройти через четыре предыдущих.

Именно эта пошаговость и делает список удобным для рекурсии: функция обрабатывает текущий узел и передаёт следующий сама себе. Разбор с кодом стоит сначала повторить на бумаге, а потом уже запускать.