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

1. Что такое модуль?

2. Какие существуют стандартные модули в системе Paskal?

3. Файл какого типа получается после трансляции модуля Paskal?

4. Какова структура модуля в Paskal?

5. Каково назначение интерфейсного разделяя модуля?

6. На какие типы можно разделить модули?

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

Цель: Сформировать умения решать нетиповые задачи с использованием рекурсивных процедур и функций

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

• прямая рекурсия;

• косвенная рекурсия.

Прямая рекурсия - функция вызывает непосредственно саму себя. Изображение прямой рекурсии на функциональной схеме программы приведено на рис. 5.1.

Рис. 5.1 - Изображение прямой рекурсии

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

ПРИМЕЧАНИЕ: Косвенная рекурсия на практике используется довольно редко, и здесь рассматриваться не будет.

Рис. 5.2 - Изображение косвенной рекурсии

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

function fact(n:byte):longint;

begin

if n=1 then fact:=1

else fact:=n*fact(n-1);

end;

В первой строчке тела функции осуществляется проверка выхода из рекурсии: факториал числа один равен самому числу. Во второй строчке осуществляется умножение значения параметра n, приведенного к вещественному числу, на рекурсивный вызов функции, в которую в качестве параметра передается значение n уменьшенное на один.

Таким образом, вычисление, например, факториала числа пять будет иметь следующую последовательность вызовов:

Fact(5)

5*Fact(4)

4*Fact(3)

3*Fact(2)

2*Fact(1)

1

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

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

Задания:

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

1. Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.

2. Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.

3. Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.

4. Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.

5. Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.

6. Реализовать рекурсивную функцию, находящую значение n-й степени числа x по формуле: x⁰=1, xⁿ = x·x^n-1 при n > 0, xⁿ=1/x^-n при n<0 (x>=0 - вещественное число, n - целое).

7. Реализовать рекурсивную функцию, находящую приближенное значение корня k-й степени из числа x по формуле: y(0) = 1, y(n+1)=y(n)-[y(n) - x / y(n)^k-1]/k, (x - вещественный параметр, k и n - целые; x > 0, k > 1, n > 0).

8. Реализовать рекурсивную функцию C(m,n) целого типа, находящую число сочетаний из n элементов по m, используя формулу: C(0,n) = C(n,n) = 1, C(m,n) = C(m,n-1) + C(m-1,n-1) при 0<m<n (m и n - целые параметры; n>0, 0<=m<=n).

9. Реализовать рекурсивную функцию NOD(A,B) целого типа, находящую наибольший общий делитель двух натуральных чисел A и B, используя алгоритм Евклида: NOD(A,B) = NOD(B mod A,A), если A <> 0; NOD(0,B) = B.

10. Реализовать рекурсивную функцию вычисления n-го числа из последовательности Фибоначчи по формуле: Fin(1)=1; Fib(n)=Fib(n-1)+Fib(n-2).

11. Дан массив целых положительных чисел (размер и элементы массива вводит пользователь) и целое число. Расставить операции сложения и вычитания между элементами массива так, чтобы получилось верное равенство с введенным целым значением.