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;

      }


 

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

52375. Великобританія. Great Britain 233.5 KB
  London is the capital of the United Kingdom of Great Britain ad Northern Ireland. It stands on the river Thames. London consists of four parts: East End, West End, City and Westminster Abbey. Great Britain is a parliamentary monarchy. The head of the state is king or queen. The British Parliament consists of two Houses: the House of Commons and the House of Lords.
52376. Discover Britain. Travelling to London 149.5 KB
  The form of our today’s lesson is a bit unusual. Today we’ll have a short competition between two teams. At our lesson you will make a trip to London. During our trip we shall have several stops. We’ll visit these stations and do the tasks at each station. Let’s divide into two teams. I’ll give you the parts of two pictures. You have to match them. What kind of picture have you got? OK. Now we have got two teams. You have to choose the captain and the name of your team.
52377. The United Kingdom of Great Britain 36 KB
  I’m glad to see you today. I’m happy to work with you, our topic is very interesting and exciting, because we are going to take a trip to one of the most beautiful countries of Europe. I want you to be positive, I want you to be in a high spirit today, I hope you’ll get bright impressions about our meeting. I do my best to make our trip memorable and interesting.
52378. Значення дихання. Будова і функції верхніх органів дихання 532 KB
  Він включає систему уроків з теми Дихання у відповідності до нової програми. У посібнику є додатковий пізнавальний матеріал схеми таблиці використаний метод проектів у вигляді презентації для подачі різних етапів уроку Значення дихання. Будова і функції верхніх органів дихання. Значення дихання.
52379. Урок: подготовка и проведение 282.5 KB
  Урок закрепления знаний и способов деятельности запоминание. Урок комплексного применения знаний умений применение. Урок обобщения и систематизации знаний и способов деятельности обобщение и систематизация. На этих уроках учитель показывает важность ключевых вопросов учебного материала его связь с другими разделами курса место в системе знаний по предмету.
52380. Побудова зображення будинку у кутовій перспективі 11.81 MB
  Поглибити знання учнів про просторові відношення на основі використання законів лінійної перспективи розширити знання про лінію горизонту. Обладнання: відеоряд картин художників різних епох і фотографій архітектурних споруд плакати з прикладами визначення різних видів перспективи і побудови геометричних предметів у перспективі презентація до уроку; альбоми графітові олівці гумки. Лінійна перспектива вид перспективи що показує у скільки разів зменшиться віддалена частина предмета в порівнянні з наближеною завдяки чому з'являється...
52381. Будова речовини. Атоми та молекули. Взаємодія молекул. Явище дифузії 74 KB
  Мета: вдосконалити уявлення та знання учнів про атоми та молекули та взаємодію; сформувати знання учнів про явище дифузії та дослідити залежність швидкості процесу дифузії від температури; формувати в учнів науковий світогляд інтерес до фізики розвивати уяву учнів спонукати їх до самовдосконалення та самореалізації. Учитель фізики. Формування нових знань Учитель фізики. Учитель фізики.
52382. Розробка бінарного уроку на тему: «Вплив податкової системи на формування державного бюджету» 534 KB
  Згідно даних динаміки доходів Держбюджету України за 2003-2010 роки найбільшим джерелом доходів держбюджету є податок на додану вартість. Другим за величиною джерелом надходжень до бюджету є податок на прибуток підприємств. Вплив держбюджету на розвиток економіки Підприємство сплачує до дохідної частини держбюджету три основних види податків: акцизний збір податок на додану вартість податок на прибуток. Є ціле розмаїття податків про яких багато хто навіть і не чули 1 ведучий Податок на...
52383. Сімейний бюджет. Доходи і витрати сім’ї 138 KB
  Доходи і витрати сімї. Мета: поглибити знання про доходи сімї як джерело збільшення її багатства; види доходів витрати обовязкові платежі бюджет родини; вчити планувати бюджет родини раціонально розраховувати витрати і співставляти їх з доходами; усвідомити свою роль у формуванні сімейного бюджету; виховати грамотного споживача та дбайливого господаря. Основні поняття: доходи витрати бюджет сімї збалансований бюджет надлишковий бюджет дефіцитний бюджет....