Рекурсивные функции

Курс по Python: https://stepik.org/course/100707

На этом занятии речь будет идти о рекурсивных функциях. То есть, о функциях, которые вызывают сами себя.

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

Итак, сразу к примеру. Вот простая рекурсивная функция:

def recursive(value):
    print(value)
    recursive(value+1)

Давайте ее вызовем с начальным значением один и посмотрим, что получится:

recursive(1)

Смотрите, функция 996 раз вызвала саму себя и произошла ошибка – достигнута максимальная глубина рекурсии. Что это за глубина и как все это работает? Сейчас все узнаете.

Когда вызывается какая-либо функция, то она помещается в стек вызова функций, в котором хранится порядок вызова различных функций. Затем, выполняется тело функции и здесь у нас снова встречается вызов той же самой функции, но с аргументом на единицу больше. Соответственно, в стеке появляется новая запись. Далее, все повторяется до тех пор, пока этот стек полностью не заполнится и не произойдет уже известная нам ошибка.

Что же сделать, чтобы такой ошибки не возникало? Очевидно, нужно ограничить глубину рекурсии. То есть, у любой рекурсивной функции должно быть условие останова, чтобы она не продолжалась вечно. В нашем случае условие для прерывания дальнейшей рекурсии можно записать, следующим образом:

def recursive(value):
    print(value)
    if value < 4:
        recursive(value+1)

В этом случае функция будет вызвана ровно четыре раза. И в консоли увидим значения от 1 до 4. А теперь последний штрих для истинного понимания работы рекурсии. После условия запишем еще один вызов функции print():

def recursive(value):
    print(value)
    if value < 4:
        recursive(value+1)
    print(value)

Запускаем программу и видим сначала увеличение переменной value, а затем, уменьшение. Что за магия? Откуда взялось это уменьшение? Как всегда, все просто. Вначале вызывается recursive(1) и печатается значение 1, затем, по рекурсии переходим к recursive(2), выводится 2 и так до 4. Когда значение value становится равным 4, условие становится ложным и рекурсия прекращается. Но после условия записана функция print(), которая выведет текущее значение переменной value, то есть, 4. Что будет дальше? А дальше текущая функция завершает свою работу, она извлекается из стека и управление передается предыдущей функции. А предыдущая функция – это recursive(3), в которой первые две команды уже выполнены и осталась одна – последний print(3), который печатает значение 3. Эта функция также завершается, извлекается из стека и мы попадаем в функцию recursive(2), где также осталось выполнить последнюю строчку print(2) – напечатать 2. И так до самой вершины, где печатаем 1. Вот теперь, вы знаете, как работают рекурсивные функции.

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

n! = (n-1)! * n

и так далее:

(n-1)! = (n-2)! * (n-1)

…

2! = 1 * 2

1! = 1

Чем нам это может помочь? Если ввести функцию:

fact(n) = n!

То этот факториал можно вычислить по рекурсии:

fact(n) = n * fact(n-1)

Именно ее мы сейчас и реализуем:

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

Вначале проверяем, если параметр n меньше или равен нулю, то возвращаем единицу, тогда fact(0) будет равен 1. А иначе идем по рекурсии, уменьшая значение n, то есть, мы будем устремляться к нулю. В итоге, у нас будет формироваться последовательность:

n * (n-1) * (n-2) * … * 1

Запустим эту функцию при n = 6 и видим в консоли значение 720, что верно:

res = fact(6)
print(res)

Второй пример будет связан с рекурсивным обходом каталогов и файлов. Так как пока мы с вами не работали с файловой системой, то для имитации структуры файлов, я создам следующий словарь:

F = {
    'C:': {
        'Python39': ['python.exe', 'python.ini'],
        'Program Files': {
            'Java': ['README.txt', 'Welcome.html', 'java.exe'],
            'MATLAB': ['matlab.bat', 'matlab.exe', 'mcc.bat']
        },
        'Windows': {
            'System32': ['acledit.dll', 'aclui.dll', 'zipfldr.dll']
        }
    }
}

А для обхода этой коллекции запишем следующую рекурсивную функцию:

def get_files(path, depth=0):
    for f in path:
        print(" "*depth, f)
        if type(path[f]) == dict:
            get_files(path[f], depth+1)
        else:
            print(" "*(depth+1), ", ".join(path[f]))

Вначале, при запуске, мы ей передадим исходный словарь:

get_files(F)

Затем, в цикле будем перебирать ключи этого словаря. В данном случае, он один – это строка ‘C:’. Отображаем этот ключ с отступом в depth пробелов от левого края и проверяем, является ли значение этого ключа словарем. Если так, то имеем набор вложенных каталогов, которые также перебираются этой же функцией, вызванной по рекурсии и с отступом на один больше. В рекурсиях отображаем все вложенные каталоги (ключи вложенных словарей), а если встречается список, то рекурсия останавливается, а список файлов отображается через запятую.

После запуска программы, видим в консоли структуру каталогов и файлов в соответствии со словарем F. Вот так, достаточно просто можно реализовать перебор иерархических данных с помощью рекурсивных функций. В подобных задачах они незаменимы и часто используются на практике.

На этом мы завершим наше занятие. Из него вы должны хорошо себе представлять работу рекурсивных функций. Выполните практические задания для закрепления материала и жду всех вас на следующем уроке.

Курс по Python: https://stepik.org/course/100707

Рекурсивные функции

Видео по теме