Рекурсия. рекурсия. Лабораторная работа Вычислительная рекурсия Вариант 10 Математическая модель формулы
 Скачать 168.91 Kb.
|
|
Лабораторная работа 2. Вычислительная рекурсия Вариант 10  Математическая модель формулы. Например, возьмем в пример число 5. Для заданного целого n вычислим значение суммы. Будет это выглядеть следующим образом: опираясь на формулу, нам нужно будет просуммировать числа от 1 до 5. Получится число 15. Единицу делим на получившееся число. 1/15=0,067. Такой должен получится ответ. Реализуем этот код в Вижуал Студио.  В static public int sum(int n) у нас происходит рекурсия. Код будет перебирать значения начиная от 5 до 2, когда мы дойдем до единицы, мы возвращаем единицу и завершаем программу.  Получим такой вот результат. Ответы на вопросы: Из каких частей состоит рекурсивное определение? Рекурсивное определение состоит из двух независимых частей: базовой и рекурсивной. Базовая часть не является рекурсивным утверждением, она задает определение для некоторой фиксированной группы объектов и определяет условие окончания рекурсии. Рекурсивная часть определения записывается так, чтобы при цепочке повторных применений она редуцировалась бы к базе. 2.Из каких частей состоит рекурсивный алгоритм? Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе. В технике процедурного программирования данное понятие распространяется на функцию, которая реализует решение отдельного блока задачи посредством вызова из своего тела других функций, в том числе и себя самой. Если при этом на очередном этапе работы функция организует обращение к самой себе, то такая функция является рекурсивной. Что такое прямая и косвенная рекурсия? Косвенная (взаимная) рекурсия – это последовательность взаимных вызовов нескольких функций, организованная в виде циклического замыкания на тело первоначальной функции, но с иным набором параметров. Прямая рекурсия – это непосредственное обращение рекурсивной функции к себе, но с иным набором входных данных. Рекурсивная триада – это этапы решения задач рекурсивным методом. Рекурсивная функция – это функция, которая в своем теле содержит обращение к самой себе с измененным набором параметров. Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма. Сравните итеративную и рекурсивную организацию вычислительного процесса. Чем они отличаются? Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце. Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел, чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя. Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.  тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел Рекурсивный процесс — это процесс с отложенным вычислением. Итеративный процесс постоянно говорит «я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда считает все в первый возможный момент, и каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается из шага в шаг. Когда итеративный процесс считает факториал 6, то ему не нужно запоминать числа. Нужно лишь считать и передавать результат дальше, в новый вызов. Когда мы находимся в очередном вызове функции, снаружи этого вызова в памяти ничего не нужно запоминать.  Что такое бесконечная рекурсия? Какова причина ее возникновения? При реализации рекурсивного вызова разработчик конфигурации должен обеспечить выход из рекурсии по какому-либо условию и не допустить бесконечной рекурсии. Следует учитывать, что на каждом уровне вызова процедуры система использует некоторое количество памяти. Если возникает бесконечная рекурсия, то сначала происходит «зависание» системы, так как выполняется многократный вызов процедуры, а потом, когда исчерпывается доступная память, происходит аварийное завершение. При этом система не может диагностировать такую ошибку, как ошибку выполнения модуля, так как нет возможности определить, когда рекурсия соответствует замыслу разработчика, а когда рекурсия становится бесконечной из-за ошибки в алгоритме. Поэтому при ошибке в модуле, приведшей к бесконечной рекурсии, не выдается сообщение об ошибке встроенного языка, а происходит аварийное завершение работы системы. Что такое уровень рекурсии? Что такое глубина рекурсии? Глубина и уровень рекурсии Максимальное число рекурсивных вызовов функции без возвратов называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени называется текущим уровнем рекурсии. В рассмотренном примере, если пользователь ввел число n=5, то общее количество вызовов функции fact равно 5, а глубина рекурсии (количество рекурсивных вызовов) равна 4. При первом вызове функции fact (в качестве одного из параметров функции printf) текущий уровень рекурсии считается равным нулю, т.к. функция еще не успела вызвать саму себя. Поскольку имена параметров и локальных переменных не меняются при каждом рекурсивном вызове, то воспользоваться значением некоторой переменной i-го уровня рекурсии можно, находясь только на этом i-м уровне. В рассмотренном примере у функции fact нет локальных переменных, но есть параметр i, область видимости которого соответствует данному правилу. Каким образом используются фреймы активации в процессе работы рекурсивного алгоритма? Фрейм активации Каждое обращение к процедуре вызывает независимую активацию этой процедуры. С процедурой принято связывать некоторое множество локальных объектов (переменных, констант, типов и процедур), которые определены локально в этой процедуре, а вне ее не существуют или не имеют смысла. Совокупность данных, необходимых для одной активации называется фреймом активации. Фрейм активации содержит независимые копии всех локальных переменных и формальных параметров процедуры, в которых оставляют "следы" операторы текущей активации. Если процедура обращается к себе несколько раз, образуется несколько одновременно существующих активаций и, соответственно, несколько фреймов активации. Обычно все фреймы являются различными экземплярами одной и той же структуры и размещаются в стеке. При некотором количестве вызовов возможно переполнение стека. На размер фрейма активации влияет способ передачи параметров в процедуру: при использовании параметров-переменных фрейм содержит адреса данных (по 4 байта на каждый параметр), а при использовании параметров-значений - сами данные, которые могут занимать достаточно много места (например, массивы). Размер фрейма активации можно примерно определить следующим образом: V= <размер области параметров>+4(адрес возврата)+2..8(для сохранения содержимого регистров)+<размер области локальных переменных>+<размер строки результата, если это функция, возвращающая результат - строку> Что такое бэктрекинг? Как реализуются алгоритмы поиска с возвратом? Поиск с возвратом, бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п. Термин backtracking был введен в 1950 году американским математиком Дерриком Генри Лемером. Незначительные модификации метода поиска с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ, поиск в глубину, метод проб и ошибок и т. д. Поиск с возвратом практически одновременно и независимо был изобретен многими исследователями ещё до его формального описания Поиск с возвратом (Backtracking) Другое важное применение стеков - поиск с возвратом (backtracking). Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной точки до пункта назначения. Начнем с одной точки. Чтобы добраться до конечного пункта, есть несколько путей. Предположим, мы выбрали случайный путь. Следуя определенному пути, мы понимаем, что выбранный нами путь неверен. Поэтому нам нужно найти способ, с помощью которого мы можем вернуться к началу этого пути. Это можно сделать с использованием стеков. С помощью стеков мы запоминаем точку, в которой мы достигли. Это делается путем добавления этой точки в стек. В случае, если мы окажемся на неправильном пути, мы можем извлечь последнюю точку из стека и, таким образом, вернуться к последней точке и продолжить наш квест, чтобы найти правильный путь. Это называется поиском с возвратом (backtracking). Прототипом примера алгоритма поиска с возвратом является поиск в глубину, который находит все вершины графа, которые могут быть достигнуты из указанной начальной вершины. Другие приложения поиска с возвратом включают поиск в пространствах, представляющих потенциальные решения проблемы оптимизации. Ветвление и ограничение - это метод для выполнения таких обратных поисков без исчерпывающего поиска всех потенциальных решений в таком пространстве. |