Раздел: Документация
0 ... 44 45 46 47 48 49 50 ... 177 154 * Глава 4. Программирование 4.8. Рекурсия Рекурсией в нгюграмм1Грованин называется вызов подпрограммой самой себя. Рекурсия является одной из пших мжшл структур упрлвлс-лим. так как с се использованием максимально просто реализуется ряд чрезвычайно полезных алгоритмов, В том, что функция может вызвать саму себя, нет ничего удивительного. Чтобы понять это, нужно четко отделить программу, определяющую функцию (оиа одна), и активацию функции (их может быть несколько). Активация — это особый объект данных, создаваемый в памяти при вызове функции на основании ее определения. Проще говоря, активация - это выполняющаяся функция. Одновременно в памяти может быть несколько активаций — они образуют стек (очередь) в том порядке, в котором они были вызваны. Активация, сформированная последней, выполняется первой — и наоборот. При вызове функции, вызывающей другую функцию, создается два объекта активации: первая функция «ждет», пока выполнится вторая, и лишь затем выполняется сама. Никаких принципиальных различий от того, вызовет ли функция свое определение или определение другой функции, нет в любом случае будет создано два объекта активации. Классическим примером рекурсивной функции, приводимым практически в любой книге по программированию,, является функция, вычисляющая факториал числа (л!-1-2-3- ..(n-2)(n-l)-n). Не будем нарушать традицию и мы (см. пример 4.22). Пример 4.22. Рекурсивное вычисление факториала factorial(n) := егтог("Parameter is defined incorrectly") if n < 0 v trunc(n) * n return I if n = 0 JjbLuiu n-factorial(n - 1} faclorial(0) = 1factorial 3) = 6 factorial(S) = 120 Проанализируем работу созданной программы на примере вычисления факториала от 3. Итак, интерпретатор Mathcad добирается до строки factorial(3). При этом создается объект активации и выполняются прописанные в определении функции действия. Так как 3 - это целое положительное числа то сразу вычисляется выражение nfactorial(n- 1). При этом происходит Вызов функции factorial) со значением параметра, равным 2. Создается второй объект активации и располагается в стеке первым. Его выполнение сопровождается появлением еще двух объектов активации — со значением п-1 и п-0. При проделывании кода для верхнего н стеке объекта активации выполняется условие п-0, что сопровождается разрушением самого объекта и возвращением в точку ньгзова — нижележащую активацию функции - значения I. При этом выражение 1-factorial0) иолучаег конечное значение, и уже данный объект активации выгружается, возвратив активации с п-2 значение 1. Следующие два шага характеризуются разрушением еще двух активаций, которое сопровождается умножением передаваемой величины на 2 и 3. В результате в точку вызова функции factorialQ возвращается значение 6. Можно легко написать алгоритм, при выполнении которого рекурсивная цепь объектов активации будет неограниченной. Естественно, что это приведет к исчерпанию ре- сурсов машины и, как следствие, к зависанию Mathcad или даже операционной системы. Чтобы этого не произошло, существуют ограничения на длину рекурсивной цепи. Она не может быть длиннее 100 объектов активации. Иначе система выведет сообщение об ошибке: This evaluation can not be evaluated. It may have resulted in an overflow or infinite recursion (Это выражение не может быть вычислено. Возможно, причина в переполнении илн бесконечной рекурсии). В программировании рекурсия обычно используется в тех случаях, в которых, выражаясь языком теории алгоритмов, нужно обойти граф (дерево) неизвестной степени вложенности. Например, с ее помощью можно просмотреть все элементы вложенного массива с неизвестной структурой или решить задачу Эйлера о ходе коня (конь должен обойти шахматную доску, побывав в каждой клетке только один раз). Впрочем, очень часто посредством рекурсии весьма изящно можно решить задачи, которые при более «приземленном* подходе решаются с помощью циклов (кстати, такой задачей является задача о вычислении факториала). В качестве примера такой задачи решим знаменитую задачу Леонардо Фибоначчи, которую он сформулировал I решил в 1202 голу. Ее условие следующее. Сколько пар кроликов можно получить от одной пары за год (за два года, за а лет)? При этом используются такие допущения: каждая пара кроликов производит новую пару раз п месяц, новая пара начинает размножаться через месяц, кролики не дохнут. Пример 4.23. Решение задачи Фибоначчи посредством рекурсии Fibonacci(n) := return 1 if п = 0v п= I s ч- О while n > 2 8-8 + Fibonacci (n - 2) n n - 1 Fibonacci(O) = 1 Fibonacci(I) => 1 Fibonacci(2) = I Fibonacci{3) - 2 Fibonacci(4) - 3 Fibonacci(5) = 5 Fibonacci6) = 8 Fibonacci(I2) • 144 Идея написанного алгоритма довольно очевидна. Количество месяцев, которое отводится одной паре кроликов на размножение, передается функции Fibonacci в качестве Параметра п. В течение этого времени она произведет п-2 новых пар кроликов. Каждая пара сама начнет размножаться. Имитировать этот процесс можно рекурсивным вызовом функции Fibonacci. Однако важно учесть, что у каждой последующей пары в потомстве будет времени на один месяц меньше, чем у предыдущей. Сделать это можно, уменьшая значение п в цикле while. Справочная система Mathcad предлагает более простую с точки зрения кода, но куда более сложную для понимания программу, решающую задачу Фибоначчи. Попробуйте самостоятельно понять, как она работает. Пример 4.24. Решение задачи Фибоначчи из справки Mathcad Gbonacci(n) return fibonacci(n return I if n = I 1) + fibonaeci(ii - 2) if n > 1 return 0 if n = 0 i:=0.. 10 f := fjbonacci(0 f «(0 I I 2 3 5 8 13 21 34 55) Фибоначчи был крупнейшим математиком средневековья. И открытая им последовательность чисел — 0, 1,1, 2,3, 5, в... — имеет исключительно важное значение. Большое количество интереснейших алгоритмов сводится к числам Фибоначчи. Например, отношение двух соседних чисел Фибоначчи при п—*» дает не ЧТО иное, как золотое сечение: Заметьте также, что каждое последующее число Фибоначчи есть сумма двух предыдущих. Многие задачи решаются с использованием рекурсии очень красиво. Однако порой важно учитывать, что рекурсия куда более требовательна к ресурсам машины по сравнению с циклами. Поэтому в случае алгоритмов, требующих объемных вычислений, отдавать предпочтение все же лучше циклам, применяя рекурсию тогда, когда альтернатив ей нет. 4.9. Пример программирования: решение задачи Эйлера о ходе коня В уже изученных нами разделах этой главы было немало примеров программирования и Mathcad. Однако почти все они были или элементарными ИЛИ узкоспециальными, иллюстрирующими какую-то одну возможность. На практике же приходится создавать значительно более сложные программы. Чтобы писать подобные программы, необходим определенный опыт — одного лишь знания теории тут недостаточно. Поэтому, чтобы «набить руку», мы пешим посредством языка программирования Mathcad классическую задачу теории алгоритмов, известную как задача Эйлера о ходе коня. Условие ее следующее: конь, начав движение из произвольной клетки, должен обойти всю доску, побывав в каждой клетке только один раз. 13 традиционной постановке задачи считается, что доска имеет размеры 8xR клеток, но ее можно решать и для доски любых других размеров Задача о коне имеет долгую историю — около трех столетий. В XV1I1 веке ее решением занимались многие известные математики, однако особенно преуспел в этом Эйлер, посвятивший ей объемное сочинение. Он создал алгоритм, дающий возможность находить маршруты подбором за приемлемое время. Позже были открыты более эффективные алгоритмы: правило Ванедорфа, рамочный метод Мунка и Коллини, метод деления на четверти Поликьяка и Роже и пр. Однако полностью задача о коне не решена до сил пор. Пока никому не удаюсь найти пето что все возможные маршруты, но даже оценить нх ЧИСЛО. Достоверно известно лишь, что число маршрутов не превосходит числа сочетаний из 168 по 63 (приблизительно 10"), по больше 30 млн. Столь значительное количество маршрутов даст право уверенно утверждать, что из какой бы клет- fibonacci( 10) Gbonacci(9) = 1.618  0 ... 44 45 46 47 48 49 50 ... 177
|
