Методы

Информация, передаваемая методу и возвращаемая методом

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

Функции TwoMax информация также передается через механизм формальных и фактических параметров. Кроме того, в теле функции используется имя Max. Это глобальное имя, определенное на уровне модуля. Так что метод может использовать в своей работе информацию, заданную глобальными именами.

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

Более подробно вопросы обмена информацией метода с внешним миром мы еще будем обсуждать при рассмотрении модулей и классов.

Рекурсивные методы

Рекурсия - мощный механизм, широко применяемый в математике и программировании. Многие понятия могут быть определены рекурсивно, когда понятие определяется через само понятие. Например, понятие "идентификатор" в программировании может быть определено следующим образом:

идентификатор - это последовательность букв и цифр, начинающаяся с буквы.

Это понятие с помощью трех правил можно определить рекурсивно.

<идентификатор> ::= <буква> 
<идентификатор> ::= <идентификатор> <буква>
<идентификатор> ::= <идентификатор> <цифра>

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

Всякое корректное рекурсивное определение должно содержать базисную часть определения, не ссылающееся на само понятие.

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

Вот соответствующий пример из программистских определений:

<оператор7gt; ::= <оператор присваивания> | <оператор цикла> | <оператор выбора> 
<оператор цикла> ::= <заголовок цикла> <оператор>

Здесь оператор определяется как оператор цикла, а определение оператора цикла, в свою очередь, ссылается на оператор. Зацикливания удается избежать, поскольку есть базисный оператор - оператор присваивания, который не ссылается на понятие "оператор".

Функции, как и другие объекты, можно определять рекурсивно. Рекурсия может быть явной, когда в теле функции, явно вызывается сама функция. Неявно рекурсивная функция может создавать последовательность вызовов: $$F_0 => F_1 => \dots F_k => F_0$$. В этом случае в теле функции $$F_0$$ вызывается функция $$F_1$$, которая вызывает в свою очередь функцию $$F_2$$ и так далее, пока функция $$F_k$$ не вызовет функцию $$F_0$$.

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

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

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

Начнем с простого примера, когда можно написать рекурсивную функцию, но функция с циклом проще и эффективнее рекурсивного варианта. Давайте напишем рекурсивный вариант функции Max из предыдущего примера:

def MaxRec(ar, start,  finish):
    if start == finish : 
        return ar[start]
    max1 = ar[start]
    max2 = MaxRec(ar, start + 1, finish)
    return max1 if max1 > max2 else max2
def test8():
    d = [7, 12, 4, 21, 18]
    max = MaxRec(d, 0, len(d) - 1)
    print ("max = ", max)
test8()	

Заметьте, у рекурсивной функции всегда появляются дополнительные параметры. Функция Max всегда ищет максимальный элемент во всем списке. Рекурсивная функция за счет дополнительных параметров универсальнее, - она ищет максимальный элемент части списка, начиная от индекса start до индекса finish. Как и положено, у рекурсивной функции есть базисная, не рекурсивная ветвь, когда искомая часть списка состоит из одного элемента, то этот элемент и является максимальным. В противном случае рекурсивно находится максимальный элемент на интервале от start + 1 до finish, после чего остается сравнить на максимум два элемента - с индексом start и найденный максимум. Конечно, эта программа сложнее для понимания, чем программа Max - привычная программа с одним циклом. Заметьте, что и отладка рекурсивной программы намного сложнее, чем отладка программы с циклами. Программа MaxRec на списке из n элементов будет вызываться n раз, экземпляры вызова и нужная информация должны сохраняться в стеке и только после того, как сработает базисная ветвь рекурсивной программы начнет выполняться обратная раскрутка стека. Возникает естественный вопрос, а нужны ли рекурсивные программы, которые сами себя вызывают и столь сложны в реализации и понимании. Ответ прост - в простых ситуациях, подобных методу Max, конечно, не нужны. Но в сложных ситуациях - рекурсия незаменимый, вполне понятный инструмент, без которого обойтись довольно трудно.

В качестве примера, где рекурсия, несомненно, полезна, рассмотрим рекурсивный метод быстрой сортировки списка. Поскольку у рекурсивных методов появляются дополнительные параметры, необходимые для организации рекурсивного вызова, то полезно строить нерекурсивную обертку рекурсивного метода. Единственное назначение такой обертки - выполнить вызов рекурсивного метода, передав параметры, требуемые рекурсивному методу, просто вычисляемые в начальный момент. Метод сортировки изменяет объект, не меняя передаваемую ссылку, поэтому реализуется как процедура. Построим процедуру обертку QSort:

def QSort(ar):
    """
    Быстрая сортировка списка QSort
    вызывает рекурсивную версию QuickSort
    """
    n = len(ar)
    QuickSort(ar, 0, n-1) 

Процедуре QSort достаточно передать имя сортируемого списка, а она уже вызовет рекурсивную версию сортировки, указав, что список нужно сортировать от начального до конечного индекса.

Идея метода быстрой сортировки состоит в том, чтобы разбить исходный список на две части. В левой половине списка расположить элементы, меньшие или равные элемента, названного кандидатом (cand в реализации процедуры). В правой половинке расположить элементы, большие или равные cand. В качестве кандидата выбирается некоторый элемент списка, чаще всего, как в приводимой реализации, элемент, стоящий в середине списка. Это разбиение списка на две части можно выполнить за линейное время. В процедуре быстрой сортировки оно выполняется элегантно за один проход по списку. Если каждая половинка будет отсортирована, то и весь список будет отсортирован. Процедура QuickSort рекурсивно применяется к каждой половинке, пока сортируемая часть не сведется к одному элементу, который по определению отсортирован.

Красивое решение, которое делает эту процедуру лучшим методом сортировки для массивов с изначально случайным порядком расположения элементов.

def QuickSort(ar, start, finish):
    """
    Рекурсивная версия быстрой сортировки
    """
    if finish > start:
        mid = (start + finish) // 2
        cand = ar[mid]
        left = start
        right = finish
        while left <= right:
            while ar[left] < cand: left += 1 
            while ar[right] > cand: right -= 1
            if left <= right:
                ar[left], ar[right] = ar[right], ar[left]
                left +=1; right -=1
        QuickSort(ar, start, right)
        QuickSort(ar, left, finish)   

В данном объявлении if - ветвь QuickSort задает рекурсивную часть определения, включающую два вызова QuickSort. Базисом рекурсии является отсутствующая else ветвь, которая говорит, что пустой список или список из одного элемента считается отсортированным и ничего в этом случае делать не нужно.

Приведем тест, запускающий на выполнение процедуру QSort:

def test9():
    ar = [5, 7, -3, 8, 16, 4]
    print ("ar before sorting :", ar)
    QSort(ar)
    print ("ar after sorting :", ar)
test9() 

Результаты работы:

Можно ли написать версию быстрой сортировки без использования рекурсии? Конечно, можно. Тони Хоар - автор быстрой сортировки написал ее вначале без использования рекурсии, поскольку в первых языках программирования не было возможности определять рекурсивные методы. Но реализовать рекурсию не простая задача, требующая использования сложных структур данных. Простота рекурсивных методов во многом определяется тем, что вся сложность реализации рекурсии снимается с плеч программиста и выполняется компилятором языка программирования (интерпретатором в случае Python).

Самое приятное в процедуре быстрой сортировки это то, что этот метод эффективнее ранее рассмотренных методов сортировки с двумя встроенными циклами - пузырьковой сортировки и сортировки вставкой. Он не просто эффективнее, но качественно эффективнее, поскольку методы с циклами имеют сложность $$O(n^2)$$, а сложность быстрой сортировки в среднем - $$O(n * log(n))$$. Для реальных задач, где массивы, содержащие несколько миллионов элементов, являются нормой, быстрая сортировка работает быстрее квадратичных методов в десятки тысяч раз.

Давайте докажем, что быстрая сортировка имеет порядок сложности $$O(n * log(n)$$. Умение оценить порядок сложности алгоритма, в частности рекурсивного алгоритма, необходимая часть работы профессионального программиста.

Пусть $$T(N)$$ - время работы процедуры QuickSort при сортировке массива размера N. Учитывая рекурсивную структуру процедуры, справедливо следующее соотношение:

где $$m1 + m2 = N, T(m1), T(m2) $$- время, необходимое для решения подзадач, $$kN$$ - время, требуемое для разбиения исходного списка на две части. Ввиду случайного характера разбиения список не делится на две равные половины, так что возможно $$T(m1) < T(N/2), T(m2) > T(N/2)$$. В среднем можно считать, что $$T(m1) + T(m2)$$ и $$2*T(N/2)$$ - это величины одного порядка. Поэтому далее будем полагать, что

Сделаем еще одно предположение, не меняющее принципиально задачу, но упрощающее доказательство. Будем полагать, что

Доказательство того, что $$T(N)$$ имеет порядок сложности $$O(n * log(n)$$ буде вести по методу математической индукции.

Базис индукции - это доказательство того, что утверждение справедливо для малого значения $$N$$. Действительно, для $$N = 2$$ утверждение справедливо, поскольку список из двух элементов сортируется за конечное число операций.

Для доказательства справедливости индуктивного шага нужно доказать справедливость импликации, доказать, что если утверждение справедливо для $$N/2$$, то оно справедливо и для $$N$$.

Пусть справедливо: $$T(N/2) = O(N/2 * log(N/2)$$

Учитывая соотношение (2), запишем:

Подставляя (3) в (1), получим:

Доказательство завершено.

Рассмотрим еще одну классическую задачу, для которой существует красивое рекурсивное решение, - задачу о Ханойской башне. Содержательная постановка этой классической задачи хорошо известна, ее нетрудно найти в интернете, в частности, в моем курсе по C#. С программистской точки зрения задача ставится так: даны три списка - A, B, C. Списки B и C - пусты, элементы списка A - упорядочены. Необходимо перенести содержимое списка A в список B элемент за элементом, сохраняя в процессе переноса упорядоченность элементов в каждом списке (правило Будды). Для выполнения этого условия разрешается использовать список C. Рекурсивный вариант решения этой задачи прост, написать вариант с использованием циклов довольно сложно. Этот пример хорошо демонстрирует мощь рекурсии, которая позволяет сказать, "что нужно сделать", ограничиваясь описанием, "как это делать", только для базисной ситуации. В частности, для этой задачи базис рекурсии говорит, что если исходный список пуст, то делать ничего не нужно. Оказывается, этого и описания функции Move - функции переноса одного элемента, достаточно для решения задачи в целом, возлагая всю тяжесть решения на реализацию рекурсивных вызовов. Приведу элегантное описание рекурсивной функции, дающей решение этой задачи:

def Move(a, b):
    b.append(a.pop())    
    
def Hanoi(n, a, b, c):
    """
    Ханойская башня
    """
    if n > 0:        
        Hanoi(n - 1, a, c, b)        
        Move(a, b)        
 Hanoi(n - 1, c, b, a)

Рекурсивное описание решения задачи выглядит так. Для переноса n элементов из списка A в список B, достаточно перенести (n - 1) элемент из списка A в список C, используя список B. Эту операцию и выполняет первый рекурсивный вызов. После чего оставшийся элемент списка A необходимо перенести в список B. Вызов метода Move позволяет выполнить эту элементарную операцию. Повторный вызов рекурсивной функции Hanoi переносит (n - 1) элемент из списка С в список B. Задача решена. Правило Будды при этих вызовах не нарушаются.

Для переноса n элементов требуется выполнить $$2^n - 1$$ ходов. Давайте строго докажем справедливость этого утверждения. Пусть P(n) - число ходов, которые необходимо сделать для переноса n элементов. Из структуры рекурсивной процедуры Hanoi следует:

Доказательство того, что:

будем вести методом математической индукции.

Базис индукции при n = 1 справедлив, поскольку действительно достаточно сделать один ход для переноса одного элемента.

Пусть верно, что

Тогда, подставляя соотношение (7) в (5), получим:

Доказательство завершено.

Обычный компьютер легко справляется с этой задачей, когда n меньше 30. Но ни один компьютер мира, работая тысячелетия, не сможет решить эту задачу при n = 64, как требовал Будда. С задачами экспоненциальной сложности классические компьютеры справиться не могут для относительно небольших значений n. Для малых значений n никаких проблем не возникает. Вот пример:

def test7():
    a = [7, 6, 5, 4, 3, 2, 1]
    b = []
    c = []
    print("before")
    print ("a = ", a, "b = ", b, "c = ", c )   
    Hanoi (7, a, b, c)
    print("after")
    print ("a = ", a, "b = ", b, "c = ", c )   
test7()

Результаты выполнения: