Индукция. Рекурсия. Стек

Начну с классического примера о факториале. Факториалом целого положительного числа N называется произведение всех целых чисел от 1 до N. Например, факториал пяти равен 1*2*3*4*5, то есть 120. Факториал единицы считается равным 1.

Все понятно. Однако, существует еще один, совершенно ужасный способ объяснения, что такое факториал. Вот он:

“Факториал единицы равен 1. Факториал любого целого положительного числа N, большего единицы, равен числу N, умноженному на факториал числа N-1 .”

Если вам уже все ясно, значит вы - математический талант. Для нормальных людей поясню. Чтобы последнее предложение было понятнее, возьмем какое-нибудь конкретное N, например, 100. Тогда это предложение будет звучать так: Факториал числа 100 равен числу 100, умноженному на факториал числа 99.

Ну и что? И как же отсюда узнать, чему равен какой-нибудь конкретный факториал, скажем, факториал трех? Будем рассуждать совершенно чудовищным образом:

Смотрю в определение: Факториал трех равен 3 умножить на факториал двух. Не знаю, сколько это. Спускаюсь на ступеньку ниже.

Смотрю в определение: Факториал двух равен 2 умножить на факториал единицы. Не знаю, сколько это. Спускаюсь еще на ступеньку.

Смотрю в определение: Факториал единицы равен 1. Вот - впервые конкретное число. Значит можно подниматься.

Поднимаюсь на одну ступеньку. Факториал двух равен 2 умножить на 1, то есть 2.

Поднимаюсь еще на ступеньку. Факториал трех равен 3 умножить на 2, то есть 6. Задача решена.

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

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

Обозначим кратко факториал числа N, как Factorial(N), и снова повторим наш индуктивный способ объяснения:

“Если N=1, то Factorial(N) = 1.

Если N>1, то Factorial(N) вычисляется умножением N на Factorial(N-1).”

В соответствии с этим объяснением напишем на Паскале функцию Factorial для вычисления факториала:

FUNCTION Factorial(N: Byte): LongInt;

BEGIN

if N=1 then Factorial:=1;

if N>1 then Factorial:=N* Factorial(N-1)

END;

BEGIN

WriteLn(Factorial(3))

END.

Обратите внимание, что в программе нигде не употребляется оператор цикла. Вся соль программы в том, что функция Factorial вместо этого включает в себя вызов самой себя - Factorial(N-1).

Что же происходит в компьютере во время выполнения программы? Механизм происходящего в точности соответствует нашему рассуждению по рекурсии.

Все начинается с того, что Паскаль пробует выполнить строку WriteLn(Factorial(3)). Для этого он вызывает функцию Factorial. Выполнение подпрограммы начинается с того, что в стеке отводится место для всех формальных параметров и локальных переменных, а значит и для нашего формального параметра N. Затем фактический параметр 3 подставляется на место формального параметра N, то есть в стек в ячейку N посылается 3. Затем выполняется тело функции. Так как 3>1, то Паскаль пытается выполнить умножение 3* Factorial(3-1) и сталкивается с необходимостью знать значение функции Factorial(2), для чего вызывает ее, то есть отправляется ее выполнять, недовыполнив Factorial(3), но предварительно запомнив, куда возвращаться.

Спускаюсь на ступеньку ниже. В соседнем месте стека отводится место для N. Это уже другое N, путать их нельзя. В эту ячейку N посылается 2. Затем выполняется тело функции. Пусть вас не смущает, что Паскаль второй раз выполняет тело функции, не закончив его выполнять в первый раз. Так как 2>1, то Паскаль пытается выполнить умножение 2* Factorial(2-1) и сталкивается с необходимостью знать значение функции Factorial(1), для чего вызывает ее.

Спускаюсь еще на ступеньку. В соседнем месте стека отводится место еще для одного N. В эту ячейку N посылается 1. Затем выполняется тело функции. Так как 1=1, то Паскаль вычисляет Factorial:=1. Вот - впервые конкретное число. Затем Паскаль пытается выполнить следующую строку if N>1 then Factorial:=N* Factorial(N-1). Поскольку нельзя сказать, что 1>1, то выполнение тела функции закончено. Значит можно подниматься.

Поднимаюсь на одну ступеньку. Паскаль возвращается внутрь тела функции (той, где N=2) и успешно выполняет умножение - Factorial:=2*1=2.

Поднимаюсь еще на ступеньку. Паскаль возвращается внутрь тела функции (той, где N=3) и успешно выполняет умножение - Factorial:=3*2=6. Задача решена.

После выхода из подпрограммы место в стеке освобождается.

Итак, рекурсией в программировании называется вызов подпрограммы из тела самой подпрограммы.

Теперь поговорим о переполнении стека. Размер стека в Паскале не превышает 64K. В нашем случае в стеке одновременно хранилось три копии формальных параметров и локальных переменных. Если бы мы вычисляли факториал десяти, то копий было бы десять. В более сложных, чем факториал, задачах стек может легко переполниться, о чем Паскаль сообщает, когда уже поздно.

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

Чем плох рекурсивный стиль программирования? Если мы для решения той же задачи напишем программу не с рекурсией, а с обычным циклом, то такая программа будет выполняться быстрее и потребует меньше памяти.

Задание 124: Напишите рекурсивную функцию fib для вычисления чисел Фибоначчи.

Сортировка

Пусть имеется ряд чисел: 8 2 5 4. Под сортировкой понимают их упорядочивание по возрастанию (2 4 5 8) или убыванию (8 5 4 2). Сортировать можно и символы (по алфавиту или коду ASCII) и строки (как слова в словаре).

Сортировка - очень распространенная вещь в самых разных программах, в частности - в системах управления базами данных.

Задача: Задан массив из 100 произвольных положительных чисел. Отсортировать его по возрастанию.

Если мы не можем сходу запрограммировать задачу, нужно подробно представить себе, в каком порядке мы решали бы ее вручную, без компьютера. Как бы мы сами сортировали 100 чисел? Мы бы запаслись пустым листом бумаги из 100 клеток. Затем нашли бы в исходном массиве максимальное число и записали его в самую правую клетку, а в исходном массиве на его месте записали бы число, меньшее самого маленького в массиве (в нашем случае подойдет 0). Затем нашли бы в изменившемся исходном массиве новое максимальное число и записали его на второе справа место. И так далее.

Вот программа для 10 чисел:

CONST N = 10;

TYPE vector = array [1..N] of Word;

CONST massiv_ishodn: vector =(3,8,4,7,20,2,30,5,6,9); {Это исходный массив}

VAR massiv_rezult: vector; {Это наш пустой лист бумаги}

i: Word;

FUNCTION maximum (m:vector; N:Word; var Nomer_max: Word):Word; {Это вспомогательная функция для поиска максимума в массиве}

VAR i,max:Word;

BEGIN

max:=m[1]; Nomer_max:=1; {Это порядковый номер максимального элемента }

for i:=2 to N do if max<m[i] then begin max:=m[i]; Nomer_max:=i end;

maximum:=max

END;

PROCEDURE sortirovka (mass_ish:vector; N:Word; var mass_rez:vector); {Основная процедура сортировки}

VAR i, Nom_max:Word;

BEGIN

for i:=1 to N do begin

mass_rez[N+1-i]:=maximum(mass_ish, N, Nom_max);

mass_ish[Nom_max]:=0

end {for};

END;

BEGIN

sortirovka (massiv_ishodn, N, massiv_rezult);

for i:=1 to N do Write (massiv_rezult[i],' '); {Распечатываем отсортированный массив}

END.

Функция maximum, кроме того, что сама имеет значение максимального элемента массива, выдает еще порядковый номер максимального элемента - Nomer_max. Это называется побочным эффектом функции.

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

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

А теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы.

Вот алгоритм: Сравним первый элемент массива со вторым, и если второй больше, то ничего не делаем, а если первый больше, то меняем местами первый и второй элементы. В этом вся соль метода. Затем повторяем это со вторым и третьим элементами. Если третий больше, то ничего не делаем, а если второй больше, то меняем местами второй и третий элементы. Затем повторяем все это с третьим и четвертым элементами и так далее. Таким образом, максимальный элемент, как пузырек, поднимется у нас до самого верха.

Теперь, когда мы знаем, что элемент номер 100 у нас самый большой, нам предстоит решить задачу сортировки для массива из 99 элементов. Запускаем второй пузырек и так далее.

Метод пузырька не требует второго массива, да и сравнений здесь в два раза меньше.

Вот программа:

CONST N = 10;

TYPE vector = array [1..N] of Word;

CONST massiv: vector =(3,8,4,7,20,2,30,5,6,9);

VAR i: Word;

PROCEDURE puziryok (var mass:vector; Razmer:Word);

VAR i,m,c:Word;

BEGIN

for m:=Razmer downto 2 do begin {Всего пузырьков – 9}

for i:=1 to m-1 do begin {i увеличивается – пузырек ползет вверх}

if mass[i]>mass[i+1] then begin {Стоит ли обмениваться значениями}

c:=mass[i]; {Три оператора для обмена значений двух элементов с помощью}

mass[i]:= mass[i+1]; {транзитного элемента c}

mass[i+1]:=c

end {if}

end {for};

end {for};

END;

BEGIN

puziryok (massiv,N);

for i:=1 to N do Write (massiv[i],' '); {Распечатываем отсортированный массив}

END.

Задание 125: Отсортируйте по убыванию двумерный массив. Я имею в виду вот что:

a[1,1] >= a[1,2] >= … >= a[1,N] >=

>= a[2,1] >= a[2,2] >= …>= a[2,N] >=

>= a[3,1] >= a[3,2] >= …

Дата добавления: 2015-11-14