Индукция. Рекурсия
Понятие рекурсии – замечательное, сложное и необходимое понятие для программиста. В первый раз, однако, вы можете прочесть этот раздел «по диагонали», уяснив только общую идею и не вникая в объяснения. В дальнейшем, при необходимости, вы вернетесь к нему.
Здесь мне никуда не уйти от классического примера о факториале. Факториалом целого положительного числа 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. Задача решена!
Рассуждая таким образом, можно вычислить факториал любого числа. Этот способ рассуждения называется рекурсивным. Ну как он вам?
:
Какое отношение все это имеет к компьютерам? Дело в том, что рекурсивный способ рассуждений реализован во многих языках программирования, в том числе – и в VB. Значит, этим языкам должен быть понятен и индуктивный способ написания программ.
Обозначим кратко факториал числа N, как Factorial(N), и снова повторим наш индуктивный способ определения:
Если N=1, то Factorial(N) = 1.
Если N>1, то Factorial(N) вычисляется умножением N на Factorial(N-1).
В соответствии с этим определением, ни минуты не сомневаясь, напишем на VB функцию Factorial для вычисления факториала:
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Debug.WriteLine(Factorial(3))
End Sub
Function Factorial(ByVal N As Integer) As Long
If N = 1 Then Factorial = 1
If N > 1 Then Factorial = N * Factorial(N - 1)
End Function
Обратите внимание, как удивительно соответствует код процедуры последнему варианту нашего индуктивного способа определения. Это практически дословный перевод определения с русского на английский язык. Единственное маленькое несоответствие – это употребление слева от знака равенства слова Factorial вместо Factorial(N). Но это требование грамматики, не меняющее смысла.
Что самое удивительное – функция работает! Несмотря на то, что в программе нигде не употребляется оператор цикла. А как же получается повторение? Вся соль программы в том, что функция Factorial вместо цикла включает в себя вызов самой себя – Factorial(N-1).
Что же происходит в компьютере во время выполнения программы? Механизм происходящего необычен, но в точности соответствует нашему путешествию по ступенькам. «Мыслей много, дела мало J». Запустите проект в отладочном режиме и обязательно понаблюдайте за окнами Locals и Call Stack:
Все начинается с того, что мы щелкаем по кнопке и VB пробует выполнить строку Debug.WriteLine(Factorial(3)). Для этого он вызывает функцию Factorial. Выполнение функции начинается с того, что в памяти отводится место для всех параметров функции и ее локальных переменных (в нашем случае это единственный параметр N). Затем число 3 подставляется на место параметра N, то есть в память в ячейку N посылается 3. Затем выполняется тело функции. Так как 3>1, то VB пытается выполнить умножение 3 * Factorial(3-1) и сталкивается с необходимостью знать значение функции Factorial(2), для чего вызывает ее, то есть отправляется ее выполнять, недовыполнив Factorial(3), но предварительно запомнив, куда возвращаться.
Спускаюсь на ступеньку ниже, выполнять Factorial(2). В другом месте памяти отводится место для N. Это уже другое N, чем в Factorial(3), путать их нельзя! В эту ячейку N посылается 2 (а в той продолжает сидеть 3). Затем выполняется тело функции. Пусть вас не смущает, что VB второй раз выполняет тело функции, не закончив его выполнять в первый раз. Так как 2>1, VB пытается выполнить умножение 2 * Factorial(2-1) и сталкивается с необходимостью знать значение функции Factorial(1), для чего, недовыполнив Factorial(2),вызывает ее. Итак, уже два недовыполненных обращения к одной и той же функции ждут своего часа на довыполнение.
Спускаюсь еще на ступеньку, выполнять Factorial(1). В другом месте памяти отводится место еще для одного N. В эту ячейку N посылается 1. Затем выполняется тело функции. Так как 1=1, то VB вычисляет Factorial=1. Вот – впервые конкретное число. Затем VB пытается выполнить следующую строку if N>1 then Factorial = N * Factorial(N-1). Поскольку нельзя сказать, что 1>1, то строка не выполняется и выполнение тела функции закончено. Значит можно подниматься.
Поднимаюсь на одну ступеньку. VB возвращается внутрь тела функции (той, где N=2), имея в кармане в качестве результата единицу, и успешно выполняет умножение – Factorial = 2*1 = 2.
Поднимаюсь еще на ступеньку. VB возвращается внутрь тела функции (той, где N=3), имея в кармане в качестве результата двойку, и успешно выполняет умножение – Factorial = 3*2 = 6. Задача решена.
Все произошло так, как если бы в окне кода было не одно объявление функции Factorial , а три. Из главной процедуры мы обратились к первому, из него – ко второму, а из того – к третьему. Выполнив третье, компьютер вернулся во второе, выполнив второе – в первое, выполнив первое – в главную процедуру.
Здесь мы рассмотрели рекурсию на примере функции. Однако обращаться к самой себе может с тем же успехом и процедура. Итак, рекурсией
в программировании называется вызов метода из тела самого метода.
Пути рекурсии не всегда бывают такими короткими. Часто функция А вызывает, например, процедуру В, которая вызывает процедуру С, которая в свою очередь вызывает функцию А. Круг замкнулся – рекурсия есть!
Чем хорош рекурсивный стиль программирования? В нашей программе о факториале мы как бы и не программировали вовсе, а просто объяснили компьютеру, что такое факториал. Как бы перешли на новый уровень общения с компьютером: вместо программирования – постановка задачи.
Чем плох рекурсивный стиль программирования? Если мы для решения той же задачи напишем программу не с рекурсией, а с обычным циклом, то такая программа будет выполняться быстрее и потребует меньше памяти.
Как преимущества, так и недостатки рекурсии вы поймете на примере выполнения следующего задания:
Задание 107.
Напишите рекурсивную функцию fib для вычисления чисел Фибоначчи. В любом случае загляните в ответ.
Оглядимся вокруг. Итак, мы изучили 5 способов заставить компьютер многократно выполнять код:
- Операторы Do …. Loop
- Операторы For
- Устаревший оператор Goto
- Использование таймера
- Рекурсия
