Лабораторная работа на тему «Использование рекурсивных вызовов в программах на языке Си» для ВПИ (филиал ВолгГТУ)

Цель работы:

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

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

Что такое рекурсия?

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

Что общего и в чем разница между циклическим и рекурсивным способами организации вычислений?

Объясните термины «база рекурсии» и «шаг рекурсии». Определите базу рекурсии и шаг рекурсии для своей задачи.

Что такое «рекурсивное зацикливание»? К каким последствиям оно приводит?

Каково главное ограничение при использовании рекурсии?

Что такое явная и косвенная рекурсии?

Оцените, от чего зависит глубина рекурсии в алгоритме решения вашей задачи.

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

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

Получите вариант задания у преподавателя.

Составьте алгоритм решения задачи согласно варианту задания, оформите его в графической форме.

Используя разработанный алгоритм, напишите программу.

Отладьте разработанную программу и покажите результаты работы про­граммы преподавателю.

Составьте отчет по лабораторной работе.

Отчитайте работу преподавателю.

Дополнительные варианты заданий.

1*. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0). Написать программу поиска минимального пути для произвольной пары городов.

2*. Вычислить определитель матрицы, пользуясь формулой разложения по первой строке:

где матрица B_k получается из A вычеркиванием первой строки и k-го столбца.

3*. Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.

4*. Несколько человек должны перейти ночью реку через мост. По мосту одновременно могут пройти только 2 человека, в наличии имеется лишь один фонарик (двое переходят мост, обязательно с фонарем, затем один должен вернуться назад с фонариком). Если заданы скорости движения каждого человека s_i, написать программу, которая предложит схему прохождения всех людей через мост за наименьшее время.

5*. Задан набор слов. Построить из них любую цепочку таким образом, чтобы символ в конце слова совпадал с символом в начале следующего.

6*. Написать процедуру печати всех перестановок из n символов.