Рекурсия

                        Эпиграф:
                        def short_story():
                            print("У попа была собака, он ее любил.")
                            print("Она съела кусок мяса, он ее убил,")
                            print("В землю закопал и надпись написал:")
                            short_story()

Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что \(0!=1\), \(1!=1\). А как вычислить величину \(n!\) для большого \(n\)? Если бы мы могли вычислить величину \((n-1)!\), то тогда мы легко вычислим \(n!\), поскольку \(n!=n(n-1)\)!. Но как вычислить \((n-1)!\)? Если бы мы вычислили \((n-2)!\), то мы сможем вычисли и \((n-1)!=(n-1)(n-2)!\). А как вычислить \((n-2)!\)? Если бы... В конце концов, мы дойдем до величины \(0!\), которая равна \(1\). Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.

Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны (об этом речь пойдет позже). Также часто использование рекурсии приводит к ошибкам, наиболее распространенная из таких ошибок — бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается, пока не кончится свободная память в компьютере. Пример бесконечной рекурсии приведен в эпиграфе к этому разделу. Две наиболее распространенные причины для бесконечной рекурсии:

1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if n == 0, то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т.д.
2. Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получиться бесконечная цепочка.

Поэтому при разработке рекурсивной функции необходимо прежде всего оформлять условия завершения рекурсии и думать, почему рекурсия когда-либо завершит работу.

Наглядная иллюстрация стека при выполнении рекурсивной функции

В чём здесь соль? Если вы вычисляете 100! при помощи рекурсивной функции, то в какой-то момент будут одновременно запущены 100 вызовов рекурсивной функции, каждая из которых будет «помнить» своё состояние. Когда последний функция выполнится, стек начнёт «разматываться» обратно.

Необязательные и именованные переменные

def add5(a, b=5):
    return a + b

>>> add5(3)
8
>>> add5(3, 10)
13

При вызове функции можно не соблюдать порядок переменных, если указывать их имена при вызове:

def foo(fst, snd):
    return fst, snd
>>> foo(1,2)
(1, 2)
>>> foo(snd=2, fst=1)
(1, 2)

Кроме того, можно указать, что все переменные начиная с некоторой могут быть переданы только по имени:

def foo(fst, *, snd=None):
    return fst, snd
>>> foo(1)
(1, None)
>>> foo(1,2)
Traceback (most recent call last):
  File "< input >", line 1, in
TypeError: foo() takes 1 positional argument but 2 were given
>>> foo(1, snd=2)
(1, 2)