E max(10,10)

-------------------------------------------------------------------------------------------------------

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

1. Он явно и немедленно отыскивает максимальный элемент массива, размер которого равен 1.

2. Для N>1 код разделяет массив на два, размер каждого из которых меньше N, исходя из индуктивного предложения, находит максимальные элементы в обеих частях и возвращает большее из этих двух значений, которое должно быть максимальным значением для всего массива.

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

Лемма 1.Рекурсивная функция, которая разделяет задачу размерности N на две независимые (непустые) решающие ее части, рекурсивно вызывает себя менее N раз.

Если одна часть имеет размерность k, а другая – N-k, то общее количество рекурсивных вызовов используемой функции равно:

Решение T=N-1 можно получить непосредственно методом индукции. Если сумма размеров частей меньше N, доказательство того, что количество вызовов меньше чем N-1 вытекает из тех же рассуждений по методу индукции. Аналоги-

чными рассуждениями можно подтвердить справедливость данного утверждения и для общего случая.

На рисунке 2 показана структура (дерево) алгоритма «разделяй и властвуй» для поиска максимума. Эта структура является рекурсивной: верхний узел содержит размер входного массива; структура левого подмассива изображена слева, а правого – справа. На рисунке 2 также показано это же дерево, но с узлами, помеченными возвращаемым значением из соответствующего обращения к функции.

Рисунок 2:

-------------------------------------------------------------------------------------------------------

Алгоритм «разделяй и властвуй» разделяет представляющий задачу массив, размер которого равен 11, на массивы с размерами 6 и 5, массив с размером 6 – на два массива с размерами 3 и т.д., пока не будет получен массив с размером 1

(верхний). Каждая окружность на этих схемах представляет вызов рекурсивной функции для расположенных непосредственно под ней узлов, связанных с ней линиями (квадраты представляют вызовы, для которых рекурсия завершается). На схеме в центре показано значение индекса в середине файла, который использовался для выполнения разделения; на нижней схеме показано возвращаемое значение.

-------------------------------------------------------------------------------------------------------