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

# Лабораторная работа № 2
## Подпрограммы и рекурсивные алгоритмы

*Цель работы:* изучение метода последовательной детализации при разработке программ;
получение навыков работы в создании и использовании подпрограмм; научится строить и применять рекурсивные алгоритмы для решения прикладных задач.

### Основные темы и алгоритмические структуры для предварительного изучения:
1. Разбитие задачи на отдельные подзадачи (подпрограммы..
2. Организация процедур и функций, вложенных подпрограмм.
3. Организация обмена данными между основной программой и подпрограммой.
4. Использование служебных слов: *exit*, *break*, *forward*.
5. Организация рекурсивных подпрограмм.
6. Составление рекуррентных соотношений и их кодирование.

### ЗАДАНИЯ:
*Задание 1:* Реализовать подпрограмму для выполнения указанного действия (см. в таблице с вариантами индивидуальных заданий). Протестировать разработанную подпрограмму, дополнив ее основной программой.

*Задание 2:* Составить программу с использованием рекурсивной подпрограммы, которая по заданной рекуррентной формуле (см. в таблице с вариантами индивидуальных заданий) для заданных границ интегрирования a и b вычисляет значение соответствующего определенного
интеграла. В отчете необходимо привести обоснования данных рекурсивных формул (вывод формулы).

*Задание 3:* Написать программу с использованием рекурсии (см. в таблице с вариантами индивидуальных заданий). При использовании рекурсии определить ее глубину. Оценить сложность алгоритма, быстроту выполнения и компактность кода. Сделать соответствующие выводы. В отчете привести дерево рекурсивных вызовов подпрограммы для конкретного примера входных данных.
В отчете необходимо привести для каждой задачи описание используемых подпрограмм, указав:
- заголовок подпрограммы;
- назначение подпрограммы
- входные/выходные параметры подпрограммы;
- словесный алгоритм работы.

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

*Контрольные вопросы:* дать развернутые ответы (с элементами теории, примерами, доказательствами) на два конкретных вопроса (номера вопросов см. в таблице с вариантами).

### Задание
1. Описать процедуру Two_Element(A, R, N, E1, E2), которая для заданного числа R и массива А размера N находит два различных элемента массива, сумма которых наиболее близка к числу R.
2. Написать рекурсивную функцию интегрирования выражения exp(a*x)*cos(x)^n
    - n = 0 f = exp(a*x)/a;
    - n = 1 f = exp(a\*x)(sin(x) + a\*cos(x))/(a^2 + 1)
    - n > 1 f = exp(a\*x)\*cos(x)^n\*(n\*sin(x) + a\*cos(x))/(a^2 + n^2) + n\*(n-1)/(a^2 + n^2)\*f(a, x, n-2);

3. Дано дерево глубины N (N — четное), каждая внутренняя вершина которого имеет 2 непосредственных потомка: А с весом 1 и В с весом (-1). Корень дерева С имеет вес 0. Найти все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов пути равен 0. Перебирать пути, начиная с «самого левого» и заканчивая «самым правым».

### Контрольные вопросы
1. В каких случаях целесообразно использовать именно функции? Какого типа может быть значение функции?
2. Существуют ли подпрограммы без параметров? Приведите соответствующие примеры. Дайте определение термину «параметр».