Цель работы: познакомиться с понятиями «рекурсивная функция» на языке программирования Паскаль, закрепить практические навыки программирования на примере реализации алгоритмов при помощи рекурсивных функций, научиться применять метод последовательной детализации в практическом программировании, применять функции при решении задач.
Контрольные вопросы:
1. Дайте определение рекурсивной функции.
2. Существует ли подпрограммы без параметров?
3. Чем отличается описание рекурсивной функции от описания функции?
4. Какое количество значений возвращает рекурсивная функция?
5. Какие переменные называются локальными?
6. Каким образом осуществляется обмен данными между основной программой и подпрограммой без параметров?
Задачи:
1. Написать рекурсивную функцию, которая выводит на экран строку, состоящую из одинаковых символов. Длина строки и символ являются параметрами процедуры.
2. Написать рекурсивную функцию, которая вычисляет объем цилиндра. Параметрами функции должны быть радиус и высота цилиндра.
3. Написать рекурсивную функцию, который вычисляет объем и площадь поверхности параллелепипеда.
4. Написать рекурсивную функцию, которая возвращает максимальное из двух целых чисел, полученных в качестве аргумента.
5. Вычислить и запомнить количество отрицательных элементов каждого столбца для матриц А(10,10) и В(5,7).
6. Составить программу для нахождения среднего балла группы по результатам сессии. Оценки групп сведены в матрицы А(25,5). В(23,5), С(22,5), D(24,5). Определить лучшую группу.
7. Составить процедуру – оператор для нахождения коэффициентов многочлена, равного произведению двух многочленов степени n и m. При помощи этой процедуры вычислить коэффициенты многочлена 
.
8. Даны три строки различной длины. Напечатать ту из них, где больше гласных латинских букв.
9. Даны три слова переменной длины. Составить слово, содержащее символы-цифры, входящие в данные слова.
10. Даны две квадратные вещественные матрицы 5-го порядка. Напечатать квадрат той из них, в которой наименьший след (сумма диагональных элементов), считая, что такая матрица одна.
11. Даны квадратичные матрицы А и В порядка m. Получить матрицу АВ-ВА.
12. Даны окружность радиуса r с центром в точке О с координатами 
и две точки А и В с координатами 
и 
, соответственно. Выяснить, является ли отрезок АВ диаметром заданной окружности.
13. Даны матрицы А(3,4) и В(4,6). Поменять местами наименьшие элементы матриц А и В.
14. Вычислить математическое ожидание М и дисперсию D случайной величины по ее экспериментальным значениям 
, пользуясь формулами: 
, 
.
15. Выполнить с использованием функции 
, где x, y, z – положительные числа<1.
16. Составить программу вычисления: 
.
17. Выполнить с использованием функции 
, где x, y– положительные числа<1.
18. Подсчитать число точек, находящихся внутри круга радиусом r с центром в точке с координатами (1,1); координаты заданы массивами x(20), Y(20). Расстояние точки от центра круга определить в подпрограмме.
19. Написать рекурсивную функцию present, которая возвращает процент от числа, полученного в качестве аргумента.
20. Написать рекурсивную функцию вычисления факториала.
Литературы:
Основная литература:
1. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988. - 320 с.
2. Абрамов С.А., Зима Е.В. Начала программирования на языке Паскаль. - М.: Наука, 1987. - 112 с.
3. Вирт Н. Алгоритмы и структуры данных./Пер. с англ. М.: Мир, 1989. - 360 с.
4. Грогоно П. Программирование на языке Паскаль. - М.: Мир, 1982. - 382 с.
5. Дантеманн Дж., Мишел Дж., Тейлор Д. Программирование в среде Delphi: Пер. с англ. - Киев: НИПФ “ДиаСофтЛтд.”, 1995. - 608 с.
6. Епанешников, Фолкнер Д.Р. Delphi: Пер.с англ.- М.: БИНОМ, 1995. - 464 с.
7. Орлик С.В. Секреты Delphi на примерах: - М.: БИНОМ. - 316 с.
Дополнительная литература:
1. Перминов О.Н. Программирование на языке Паскаль. - М.: Радио и связь, 1988. - 224 с.
2. Пильшиков В.Н. Сборник упражнений по языку Паскаль: Учеб. пособие для вузов. - М.: Наука, 1989. - 160 с.
3. Прайс Д. Программирование на языке Паскаль: Практ. руководство. - М.: Мир, 1987. - 232 с.
4. Рубенкинг Н. Турбо Паскаль для Windows: В 2 т.; Пер. с англ. - М.: Мир, 1993. - 536 с.
5. Фаронов В.В. Турбо Паскаль. В 3-х книгах. Книга 1. Основы Турбо Паскаля. - М.: Учеб.-инж.центр МВТУ-ФЕСТО ДИДАКТИК, 1992. - 304 с.
6. Фаронов В.В. Паскаль и Windows. - М.: Учеб.-инж.центр МВТУ-ФЕСТО ДИДАКТИК, 1994. - 539 с.
Методические указания:
Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.
Пример.
Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».
Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.
Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.
Применение рекурсии позволило решить задачу без использования циклов, как в основной программе, так и в процедуре.
Program Arsac;
Var first: word;
Procedure posledov (i: word);
Begin
Writeln (i);
If i=1 then exit;
If odd(i) then posledov(3*i+1) else posledov(i div 2);
End;
Begin
Write (‘ введите первое значение ’); readln (first);
Posledov (first);
Readln;
End.
Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F(N) может понадобиться вычислить F(N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.