Python. Рекурсия. Что это?

Рекурсия — это когда функция вызывает саму себя изнутри. Ну вот на примере факториала:

def factorial(n): # объявление 
    if n == 0: # если n == 0, то...
        return 1 #... то n!=0!=1, верно?
    else: #А если не 0, то...
        return n * factorial(n - 1) #n! = n * (n - 1)! и вызывает эту функцию для значения меньшего на 1.

Так понятно?

Вы вызываете функцию факториала, допустим, с числом 2:

1. Условие if n == 0 не выполняется, функция идёт дальше.

2. (factorial(n - 1)). Всё повторяется, но с n, уменьшенным на 1. Теперь условие снова не выполняется и функция вызывается ещё раз, но с числом 0.

3. Условие наконец выполнится и вернёт 1.

4. Потом поднимаемся вверх до функции, вызванной с числом 1. Она вернёт 1 * 1 (т.к. функция ниже вернула 1), и ещё выше передаст свой результат, в данном случае - 1. Потом самая верхняя функция умножает результат предыдущей (1) на 2 и возвращает 2 в основной поток.