100788

Рекурсивные функции

Лабораторная работа

Информатика, кибернетика и программирование

Приведите примеры рекурсивных объектов и явлений. Обоснуйте проявление рекурсивности. Почему при правильной организации рекурсивные вызовы не зацикливаются. Почему не отождествляются совпадающие идентификаторы при многократных рекурсивных вызовах. Почему рекурсивные обращения завершаются в порядке, обратном вызовам этих обращений. Чем ограничено при выполнении программы количество рекурсивных вызовов...

Русский

2018-04-07

73 KB

1 чел.

Лабораторная работа № 9.

Тема:

Рекурсивные функции.

Цель:

Получить практические навыки проектирования, реализации и использования рекурсивных функций, научиться использовать различные способы передачи параметров и возврата результата.

Программное обеспечение:

ОС Windows, СodeBlocks

Задача:

Написать и отладить программу, выполняющую задание. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя рекурсивные функции. Этапы сопроводить комментариями в коде.

  1. Умножить два целых числа не используя операцию умножения (рекурсивным алгоритмом).
  2. Задана матрицаn хn каждый элемент которой равен 0 или 1. Рядом стоящие по вертикали и горизонтали единицы образуют «пятна» произвольной конфигурации. Посчитать количество таких пятен.
  3. Задан лабиринт в виде матрицыn хn. Если элемент матрицы равняется 0 - проход есть, если 1 - нет. Задаются координаты входа в лабиринт и координаты выхода. Путник может перемещаться только вверх, вниз, вправо и влево. Вывести кратчайший путь от входа к выходу или сообщить что прохода нет.
  4. Посчитать количество вариантов расположения восьми ферзей на шахматный доске, так чтобы каждый из них не угрожал другому.

Содержание отчета:

Титульный лист

Порядок выполнения работы

Описание алгоритмов решения задач.

Исходный код программ по комментариями.

Результаты тестирования программ.

Выводы

Контрольные вопросы

  1. Приведите примеры рекурсивных объектов и явлений. Обоснуйте проявление рекурсивности.
  2. Почему при правильной организации рекурсивные вызовы не зацикливаются?
  3. Почему не отождествляются совпадающие идентификаторы при многократных рекурсивных вызовах?
  4. Почему рекурсивные обращения завершаются в порядке, обратном вызовам этих обращений?
  5. Чем ограничено при выполнении программы количество рекурсивных вызовов?

Общие сведения

Одной из сложных к пониманию тем в большом числе случаев оказывается тема рекурсии. Даже шутки есть:Чтобы понять рекурсию, надо сначала понять рекурсию.

В программировании рекурсией называют зацикливание функций путём вызовов функций вызовами функций.

Различают прямую рекурсию и косвенную:

Прямая – это прямой вызов из некоторой функции этой же самой функции.

Косвенная – это вызов из первой функции второй функции, когда вторая функция в своём вычислении использует первую функцию.

#include <iostream>

using namespace std;

 void foo(int x=5) {//Функция foo c одним параметром

cout << x << '\n';

if (x) foo(x-1);//Обращаемся к функции foo с одним параметром

}

 int main() {

foo();//Провоцируем запуск функции foo

return 0;

}

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

В показанном примере при каждом новом вызове функции foo мы изменяем параметр: отдаём аргумент на единицу меньший, чем последний отданный. Таким образом мы стремимся к нулю или к какому-нибудь отрицательному значению. Это значение используется как выключатель рекурсивных вызовов. Т. е. перед рекурсивным вызовом мы обязательно должны выполнять проверку, достигнута ли контрольная точка для срабатывания выключателя, если нет, то запускаем функцию снова, а если достигнута, то не вызываем функцию. Если этой проверки не сделать, то получится эффект бесконечно рекурсии, из-за которой сломается программа. Природа рекурсии – цикл, но в отличие от непосредственных циклов – рекурсия работает немного иначе, каждый рекурсивный вызов требует себе памяти. Жрёт память рекурсия с аппетитом. При большом количестве рекурсивных вызовов памяти просто не хватает, поэтому в отличие от использования обычных циклов, когда программа зависает, рекурсия программу не вешает, а обычно просто валит/ломает, при этом программа жалуется на переполнение стека.

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

Каждый новый рекурсивный вызов – это создание в памяти нового экземпляра функции. Т. е. сколько рекурсивных вызовов происходит – столько в памяти висит экземпляров функций.

Простейший пример использования косвенной рекурсии:

#include <iostream>

void foo1(int);        //Прототипыфункций

void foo2(int);

using namespace std;

void foo1(int x) {

cout << x << '\n';

foo2(x-1);          //foo1 задействует foo2

}

void foo2(int x=5){

    if (x) foo1(x);            //foo2задействует foo1

}

int main() {

foo2();       //Провоцируемзапускфункции foo2

return 0;

}

О рекурсии иногда говорят, что она не нужна, что использовать её плохо и всячески стараются очернять. На самом деле рекурсивные коды всегда выглядят лаконично и красиво. Если вы видите иерархию папок, выстроенную в виде дерева, то на 99,9% для вычисления использована рекурсия. Многие фундаментальные алгоритмы, до которых вы однажды дойдёте, если будете серьёзно изучать языки программирования, описаны с помощью рекурсивных функций. Некоторые сортировки используют рекурсивные функции (быстрая сортировка). Т. е. люди не стесняются применять рекурсивные функции, а все эти заявители о бессмысленности рекурсии могут, конечно, иметь свою точку зрения, но по-моему понимать и применять рекурсию должны уметь все, кто занимается программированием. Рекурсия является важной темой, подробно разбираемой в специальных курсах программирования.

Согласно правилам языка С++ – нельзя рекурсить функцию main.

Подобно виткам циклов, которые называют итерациями, каждый новый виток рекурсивного срабатывания иногда называют шагом рекурсии. В дальнейшем я тоже буду использовать этот термин.

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

Задача:

С помощью рекурсии вывести на экран сумму натуральных чисел от 1 до N

#include <iostream>

 using namespace std;

 //рекурсивная функция

int sum(int n)  //В качестве параметра будет передаваться число из места вызова в переменную n

{

if (n == 1) return 1;  //если новое значение 1, то будем складывать его с 1, а не с предыдущим. т. к. предыдущее - это ноль. и сложение 1+0 будет бесконечным.

else return sum(n - 1) + n;//но если n>1, то складываем его с предыдущим значением, равным сумме всех элементов до n

}

 int main()

{

cout << "1..5: " << sum(5) << endl;// передаем в функцию sum аргумент 5. n принимает значение 5

cout << "1..6: " << sum(6) << endl;// передаем в функцию sum аргумент 6. n принимает значение 6

cout << "1..7: " << sum(7) << endl;// передаем в функцию sum аргумент 7. n принимает значение 7

return 0;

}

Поскольку мы не знаем заранее, сколько у нас рекурсивных шагов получится, мы забиваем память экземплярами функций, при этом первый созданный экземпляр функции оказывается в самом хвосте отдачи результатов: функции при рекурсии срабатывают наизнанку. По этой причине мы отталкиваемся не от последнего вычисления, создавая контрольную точку, а от первого: первая рекурсивная функция выполняется последней, вторая предпоследней и т. д. Контрольной точкой в показанном примере мы сделали единицу. А чтобы эта единица могла быть достигнута, при каждом новом вызове функции мы уменьшаем уходящий в функцию аргумент на 1. Если nпринял единицу, то возвращается единица, иначе функция вызывает саму себя. Вот этот момент важно словить, это и есть рекурсия. Когда мы отдаём аргументом в функцию число 5, у нас в памяти в один момент времени оказывается 5 скопированных экземпляров функций, когда 6 – 6 экземпляров, когда 7 – 7 экземпляров.

Использование рекурсии чаще всего предполагает выполнение цепочки одинаковых функций, различающихся только приходящими в них значениями, начинать с последней созданной копии функции, т. е. обход от последнего вычисления к первому.

Вот мы запустили функцию суммирования чисел от 1 до 5. Как работает созданная нами рекурсивная функция? – Срабатывает функция sum, в которой параметр подбирает значение 5, значение параметра проверяется с контрольной точкой: 5 == 1?, поскольку равенство ложно, создаётся новый экземпляр функции, в которую уходит значение 5-1, в этом новом экземпляре проверяется равенство 4 == 1? … в какой-то момент времени в функцию отдаётся значение 2-1, проверяется равенство 1 == 1?, условие верно, функция завершается и отдаёт результатом своих действий число 1Создание цепочки копий функции, звенья которой прекращают создаваться при достижении контрольной точки, т. е. при достижении nПараметр 1: возврат 1Параметр 2: возврат sum(n-1) + n ==> sum(2-1) + 2 ==> 1 + 2 ==> 3 ==>возврат 3Параметр 3: возврат sum(n-1) + n ==> sum(3-1) + 3 ==>3 + 3 ==> 6 ==>возврат 6Параметр 4: возврат sum(n-1) + n ==> sum(4-1) + 4 ==>6 + 4 ==> 10 ==>возврат 10Параметр 5: возврат sum(n-1) + n ==> sum(5-1) + 5 ==>10 + 5 ==> 15 ==>возврат 15

В этом раскладе вам нужно понять, что sum(n-1) вычисляет некоторое значение в другом экземпляре функции, а n – это актуальное значение для текущей функции, т. е не надо думать о том, что в этой формуле обе n обозначают одно и то же значение: слева результат работы функции для аргумента n-1, а справа да, прямое значение параметра текущей функции.

  • Любую рекурсию теоретически можно заменить обычными циклами.
    • Рекурсии требуют больше времени и памяти, чем требуют обычные циклы.
      • Но иногда рекурсия способствует культуре кода, т. е. код становится читать легко и алгоритм работы понимается значительно быстрее, чем при использовании циклов для реализации того же самого алгоритма.
        • Основное достоинство рекурсии в том, что с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причём программа не будет содержать явных повторений.
          • Основной недостаток рекурсии – издержки времени на создание экземпляров функций и прожорливость к памяти.

В завершение этой статьи приведу другое решение задачи на сложение чисел использованием рекурсии:

Пример1

//Рекурсия#include <iostream>

#include <iomanip>      //setw

 

using namespace std;

 

void sum(int value, int result=0){

    if (value){

            result = value + result;

            sum(value-1, result);          //рекурсивныйвызов

    } else {

        cout << result << setw(5);          //ели достигнута контрольная точка, выводим результат на экран

    }

}

 

int main(){

 

    for (int i=0; i<50; i++){                  //Будем смотреть несколько результатов

        cout << 1 << ".." << i << " == ";

        sum(i);                                //вызовфункции sum

        cout << '\n';

    }

    return 0;

}

Пример вычисленияn! с помощью рекурсии.

Int fact (int n)

   {

int p;

if(n==1) return 1;

p=fact(n-1)*n;

    return p;

   }

int main()

     {

int a,d;

cin>>a;

if(a==0) { cout<<1;return 0; }

d=fact(a);

cout<<d;

return 0;

      }


 

А также другие работы, которые могут Вас заинтересовать

33749. Понятие, признаки и форма договора поставки 15.1 KB
  Понятие признаки и форма договора поставки.Правовая природа договора поставки консенсуальный взаимный возмездный в некоторых случаях обязательный для поставщика. Долгосрочный харр договора.Предметом договора могут быть любые не изъятые из оборота вещи как существующие в момент заключения договора так и не произведенные в момент заключения договора как правило определяемые родовыми признаками.
33750. Способы и порядок заключения договора поставки 15.03 KB
  товар передается путем отгрузки его поставщиком либо самому покупателю либо лицу указанному им; товар может быть передан на месте нахождения поставщика на основании отгрузочной разнарядки которая должна быть направлена поставщику за 30 дней до момента поставки; товар может также передаваться и на месте нахождения поставщика такая передача называется выборкой; право выбора транспорта для доставки товара принадлежит поставщику; многооборотная тара и средства пакетирования в которых Доставлен товар подлежат возврату...
33751. Содержание договора поставки 15.89 KB
  Обязанности поставщика: передать товар в обусловленный срок равномерными партиями в соответствии с установленными графиками; восполнить недопоставленный товар в следующий период; вывезти товар от которого отказался покупатель но принял его на ответственное хранение; подготовить товар к вывозу и уведомить об этом покупателя если договор заключен с условием выборки товара; выполнить указание покупателя об отгрузке заказанного им товара другому лицу; возместить расходы понесенные покупателем в связи с ответственным хранением...
33752. Ответственность сторон за нарушение условий договора поставки 14.48 KB
  Ответственность сторон за нарушение условий договора поставки. Ответственность по договору поставки в основном регламентируется общими положениями о куплепродаже но существуют следующие особенности: покупатель вправе предъявить требования предусмотренные статьей 475 ГК Последствия передачи товара ненадлежащего качества при нарушении поставщиком условий договора о качестве и комплектности товара только если поставщик незамедлительно после получения уведомления о допущенных недостатках не заменит недоброкачественный товар либо не...
33753. Прекращение договора поставки 14.05 KB
  Прекращение договора поставки. Основаниями прекращения договора поставки являются: ненадлежащее исполнение договора; соглашение сторон о расторжении договора; односторонний отказ от исполнения договора в случае существенного нарушения договора другой стороной ст. Основаниями для одностороннего отказа от исполнения договора поставки являются: нарушения допущенные поставщиком; поставка товаров с недостатками не устранимыми в приемлемый для покупателя срок п.
33754. Поставка товаров для государственных нужд 15.58 KB
  Поставка товаров для государственных нужд разновидность договора поставки. Срок выполнения действий по заключению договора ограничен законом он определен либо в 30 дней либо в 20. Особенности договора поставки для государственных нужд состоят в том что участниками этого типа договора являются три лица: заказчик; поставщик; получатель товара. Предметом вышеназванного договора являются вещи определяемые родовыми признаками; потребность в заказываемых вещах выявляется из государственных программ форма этого договора должна быть всегда...
33755. Договор контрактации, обязанности сторон 22.42 KB
  Характеристика договора контрактации консенсуальный взаимный возмездный. Разновидностью данного договора является поставка сельскохозяйственной продукции для государственных нужд. Предметом договора контрактации могут быть вещи трех видов: непереработанная продукция; переработанная продукция; сырье. Предмет этого договора не предназначен для личного семейного домашнего т.
33756. Договор о снабжении энергетическими и другими ресурсами 15.89 KB
  Договор о снабжении энергетическими и другими ресурсами. По договору энергоснабжения энергоснабжающая организация обязуется подавать потребителю абоненту энергию через присоединенную сеть а потребитель абонент обязуется оплачивать принятую энергию а также соблюдать предусмотренный договором режим ее потребления. Договор энергоснабжения является разновидностью договора куплипродажи и по своей природе двусторонний и возмездный. Особенности договора энергоснабжения: необычность электроэнергии как объекта: электроэнергию нельзя...
33757. Institute on Mathematics and Mechanics, Urals Branch of Russian Academy of Science 16.5 KB
  Semiotics, dealing with sign systems and with practice of their functioning, may be considered as tools for descriptions of theories of HCI and Computer Visualization just as Mathematics is tools for descriptions of Physics Theories.