Как объяснить человеку, что такое рекурсия?

Бессмысленно объяснять рекурсию на примере факториала. Это слишком примитивная задача для того, чтобы что-то понять.

1. Начать с объяснения, что такое стек и как он применяется на практике.
2. Разобрать задачу, легко решаемую с помощью цикла и стека и сложно решаемую только циклом (например, поиск в двоичном дереве).
3. Рассказать про аппаратный стек процессора.
4. Объяснить, что локальные переменные подпрограммы хранятся в стеке. Что вызов подпрограммы - это запись в стек, а возврат из подпрограммы - удаление из стека.
5. Перейти к рекурсивной версии алгоритма, разобранного в п.2. Показать, что рекурсия - всего лишь более удобная запись цикла + стека.
6. Перейти к теме косвенной рекурсии - например, на примере грамматического разбора методом рекурсивного спуска.

P.S. Непонимание рекурсии - это отсутствие базовой математической подготовки. Не школьной, а необходимой программисту.