Рекурсивные алгоритмы

Рекурсивные алгоритмы
Алгоритм называется рекурсивным, если на каком-­либо шаге он прямо или косвенно обращается сам к себе.
В рекурсивном определении должно присутствовать ограничение (граничное условие), при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
!
Приведите примеры рекурсии, встречающиеся в жизни, природе или литературных произведениях.
?
Ночь, улица, фонарь, аптека,
Бессмысленный и тусклый свет.
Живи еще хоть четверть века –
Все будет так. Исхода нет.
Умрешь – начнешь опять сначала
И повторится все, как встарь:
Ночь, ледяная рябь канала,
Аптека, улица, фонарь.
А. Блок

Примеры рекурсивных алгоритмов
Пример 2. Числа Фибоначчи – элементы последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … , в которой первые два числа равны 1, а каждое следующее число равно сумме двух предыдущих чисел. Запишите рекуррентное определение чисел Фибоначчи.
Ответ:
F (n) = 1 при n ≤ 2;
F (n) = F (n-1) + F (n-2) при n > 2.
Пример 3. Запишите рекуррентное определение функции, вычисляющей количество цифр в натуральном числе n.
Ответ:
К (n) = 1 при n < 10;
К (n) = К (n div 10) + 1 при n ≥ 10.