# Содержание

# Рекурсия

                        Эпиграф:
                        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)