НШ 1: Рекурсия

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

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

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

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

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

Последнее изменение: Суббота, 15 Август 2020, 02:35