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.  Реализовать программу вычисления длины строки.

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


 

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

37697. Встановлення вимог до функціональності програмного забезпечення із застосуванням засобів UML (Use Case diagram) та вербальних Специфікацій 150 KB
  Поселення відбувається портє і далі передається адміністратору для підтвердження внесення даних до БД. Адміністратор виконує всі операції з БД в тому числі: внесення змінення та видалення записів з бази а також внесення службової інформації що передбачає внесення особистих даних адміністратора та портьє. Портьє надає інформацію про поселення клієнтів адміністратору АС у вигляді: Перелік кімнат різних класів у готелі. Основний потік Надання інформації адміністратору.
37698. Визначення параметрів датчиків температури 117 KB
  Установка складається із теплового обєкта ТО резервуар з трансформаторним маслом в якому розміщені робочі гарячі спаї батареї термопар БТ резистори. Батарея термопар складається із трьох послідовно включених термопар завдяки чому її сумарна тсрмое. Холодні кінці термопар заглиблені в рідину що має температуру оточуючого середовища. За допомогою контрольного термометра ТІ вимірять температуру холодних кінців термопар t0.
37700. Критерій Стьюдента 74.92 KB
  Щільність розподілу Графік щільності розподілу Стьюдента за зовнішнім виглядом нагадує нормальні криві. Але вони значно повільніше спадають до осі t якщо особливо за малих значень n Складено таблиці розподілу Стюдента здебільшого виду для кількості ступенів волі від 1 до 20. Якщо кількість ступенів волі більша то можна застосовувати нормальний закон розподілу з нульовим математичним сподіванням і одиничною дисперсією. Щільність цього розподілу подається формулою: Щільність розподілу Фішера має графік зображений на Для розподілу Фішера...
37701. Ознайомлення з середовищем програмування. Структура програми. Програмування лінійних та розгалужених алгоритмів 1.24 MB
  Тема: ознайомлення з середовищем програмування. Структура програми. Програмування лінійних та розгалужених алгоритмів. Мета: навчитись програмувати лінійні та розгалужені алгоритми мовою програмування С.
37702. Моделювання і розробка ІС 691 KB
  У рамках Rtionl Rose використовуються наступні графічні діаграми UML: Діаграма варіантів використання дозволяє здійснити аналіз функцій системи. Діаграма класів дозволяє описати структуру інформаційних обєктів ІС. Діаграма станів дозволяє відобразити зміни станів окремого об'єкта чи субєкта ІС представляючи його у вигляді спеціального орієнтованого графа. Діаграма діяльності використовуються для опису інформаційних процесів; Діаграма послідовності служить для моделювання характеристик взаємодії передачі і прийому...
37703. Побудова локальної комп’ютерної мережі 1.95 MB
  2 Завдання: Навчитись встановлювати драйвери мережних адаптерів в середовищі операційних систем Windows 2000 XP; дослідити схеми підключення мережних пристроїв в локальній компютерній мережі топології â€зірка†та â€ієрархічна зіркаâ€; навчитись налаштовувати адресацію компютерів в локальній компютерній мережі; дослідити способи перевірки працездатності компютерної мережі за допомогою діагностичних утиліт. ІРАДРЕС МАСКУ ПОДСЕТИ ШЛЮЗ...
37705. Оцінка розміру та вартості проекту за моделлю COCOMO 64.5 KB
  Тема: Оцінка розміру та вартості проекту за моделлю COCOMO Мета: набуття навиків у прогнозуванні характеристик проектів ПЗ з використанням конструктивної моделі вартості CОnstructive CОst MОdel. Короткі теоретичні відомості COCOMO це множина моделей яка дозволяє обчислити вартість проекту ПЗ на основі одиниці виміру кількість рядків коду LOC. COCOMO включає наступні моделі: базова COCOMO застосовується у фазі специфікування вимог; проміжна COCOMO застосовується у фазах розробки множин вхідних умов проекту наприклад ...