68598

Программирование рекурсивных алгоритмов

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

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

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

Русский

2014-09-23

38.5 KB

8 чел.

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

Тема: Программирование рекурсивных алгоритмов

Цель занятия:

  •  Совершенствование навыков разработки программ в среде программирования MS Visual C++
  •  Совершенствование навыков описания и использования функций в программах
  •  Получение начальных навыков в использовании рекурсий

Время на выполнение работы: 2 часа

Учебные вопросы:

  1.  Рекурсивные определения и алгоритмы
  2.  Программирование рекурсий

Подготовка к выполнению работы:

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

Материалы для подготовки к занятию:

  1.  Конспект лекций.
  2.  [1] стр. 73-82.


ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

  1.  Рекурсивные определения и алгоритмы

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

Классическим примером рекурсивной функции является вычисление факториала числа. Для того чтобы получить значение факториала числа n, требуется умножить на n факториал числа (n-1). Известно также, что 0!=1 и 1!=1.

Рассмотрим реализацию рекурсивной функции для вычисления факториала числа:

long fakt (long n)

{

if (n==0 || n==1) return 1;

return (n*fakt(n-1));

 }

То же самое можно записать  короче:

long fakt(long n)

{

return (n>1)?n*fakt(n-1):1;

 }

Рассмотрим реализацию этой же задачи без использования рекурсии:

Long fakt(int n)

{

long m=1;

for (int i=2;i<=n;i++)

 m*=i;

 return m;

}

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

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

  1.  Программирование рекурсий

Рассмотрим еще один пример функции, с которой мы уже знакомились на практическом занятии №7 – функция определения длины строки strlen(s). Учитывая, что элементы любого массива расположены друг за другом и любой строковый массив заканчивается символом окончания строки «\0», то можно рекурсивно вызывать функцию определения длины строкового массива (или строки):

int lengh(char *a)

    {

    static int n=0;

    n++; a++;

    return (*a!='\0')?lengh(a):n;

    }

Разберем работу этой рекурсивной функции.

В функцию передается указатель на строку, длину которой необходимо определить. В функции объявляется статическая переменная, задача которой – подсчет количества вызовов функции, что и будет говорить о длине строки. При каждом вхождении в функцию ее значение увеличивается на 1. Так же, при каждом вхождении в функцию адрес начала строки увеличивается на 1, что соответствует уменьшению строки на один символ, на который увеличилась подсчитываемая длина строки. Этот процесс будет продолжаться до тех пор, пока указатель на текущий элемент строки не укажет на символ окончании строки, что и будет признаком окончания рекурсивного вызова функции. В завершении целесообразно привести текст функции main(), в которой происходит вызов рассмотренной рекурсивной функции:

int main(int argc, char* argv[])

{

char str[50]; int n=0;

cout<<"\Input the string: ";

cin>>str;

n=lengh(str);

cout<<endl<<n;

return 0;

}

ПРОГРАММА  РАБОТЫ

  1.  Реализовать программу вычисления факториала числа.
  2.  Реализовать программу вычисления длины строки.

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


 

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

26798. Основы методологии проектирования ИС 152 KB
  В общем виде цель проекта можно определить как решение ряда взаимосвязанных задач включающих в себя обеспечение на момент запуска системы и в течение всего времени ее эксплуатации: требуемой функциональности системы и уровня ее адаптивности к изменяющимся условиям функционирования; требуемой пропускной способности системы; требуемого времени реакции системы на запрос; безотказной работы системы; необходимого уровня безопасности; простоты эксплуатации и поддержки системы. Конечными продуктами этапа проектирования являются: схема базы...
26799. Информационные системы. Основные понятия. Корпоративные информационные системы. Структура КИС 469.61 KB
  Корпоративные информационные системы. взаимосвязанные функциональные подсистемы обеспечивающие решение задач организации. Функциональные подсистемы в принципе не могут существовать без компьютерной инфраструктуры.
26800. История развития баз данных 420.15 KB
  И в этом случае наличие сравнительно медленных устройств хранения данных к которым относятся магнитные ленты и барабаны было недостаточным. Эти устройства внешней памяти обладали существенно большей емкостью чем магнитные барабаны обеспечивали удовлетворительную скорость доступа к данным в режиме произвольной выборки а возможность смены дискового пакета на устройстве позволяла иметь практически неограниченный архив данных. До этого каждая прикладная программа которой требовалось хранить данные во внешней памяти сама определяла...
26801. Линейное программирование шпаргалка 136.17 KB
  Чтобы отделить корень графически необходимо построить график функции fx на промежутке изменения x тогда абсцисса точки пересечения графика функции с осью ОХ есть корень уравнения. Этот метод можно получить из метода Ньютона заменив производную отношением разности функции к разности аргумента в окрестности рассматриваемой точки...
26802. Четыре уровня модели TCP/IP стека 333.62 KB
  Уникальный 32битный IPадрес в InterNet. IPv6 адрес является уникальным 128битным идентификатором IPинтерфейса в Интернет иногда называют Internet2 адресного пространства IPv4 уже стало не хватать поэтому постепенно вводят новый стандарт. IANA The Internet Assigned Numbers Authority Управление назначением адресов в Internet организация осуществляющая контроль над распределением доменов первого уровня.ru internet index.
26803. Метод Эйлера решения задачи Коши для ОДУ 1-го порядка 260.5 KB
  Можно рассматривать и несколько иную классификацию ИП: сбор подготовка передача хранение накопление обработка представление информации. Поиск информации. Поиск или сбор информации первичный информационный процесс лежащий как правило в сфере некоторой практической или научной деятельности. Поиск информации это извлечение хранимой информации.
26804. Одномерная оптимизация 79 KB
  Система должна предусматривать режимы ведения системного каталога отражающего перечень областей знаний по которым имеются книги в библиотеке. Каждая книга хранящаяся в библиотеке характеризуется следующими параметрами: уникальный шифр; название; фамилии авторов могут отсутствовать; место издания город; издательство; год издания; количество страниц; стоимость книги; количество экземпляров книги в библиотеке. Книги могут иметь одинаковые названия но они различаются по своему уникальному шифру ISBN. Читатель не должен одновременно...