Rekursia

Рекурсия – способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
Числа Фибоначчи
F1 = F2 = 1;
Fn = Fn-1 + Fn – 2
для n > 2
Примеры рекурсий:
Фракталы - треугольник Серпинского, фигуры обладающие свойствами самоподобия

У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…

Рекурсивная процедура (функция) – это процедура(функция), которая вызывает сама себя напрямую или через другие процедуры и функции.
def df(n):
if n == 0:
return 1
else:
df(n // 2)
print(n % 2, end = '')
df(int(input()))
Рекурсия заменяет цикл

Задача: Вычислите сумму всех цифр числа
def df(n):
s = n % 10 if n >= 10:
s += df(n // 10)
return s
print(df(89)))
df(89)
9 + df(8)
9 + 8