Рекурсивные функции

Лабораторная работа №1

Рекурсивные функции

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

 

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

 
Общие сведения

При первичном осмыслении понятие  рекурсии достаточно просто и не требует  специальных знаний. Иногда на рекурсию смотрят как на наличие в определении  объекта ссылки на сам объект или проявление свойств самоповторения (при этом сколь угодно малая часть объекта подобна всему объекту в целом). Общий случай проявления рекурсивности может быть сформулирован как наличие циклических взаимных обращений в определении объекта, которые в итоге замыкаются на сам объект.

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

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

Рекурсия в широком  смысле – это определение объекта посредством ссылки на себя.

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

Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.

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

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

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

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

Пример 1. Вычислить значения функции f(x)=2 cos x+3, при x={1; 4; 7,5; 20}. Вывести результаты в два столбца: в первом - значения x, во втором - значения f(x). Вычисления провести двумя способами: с помощью функции и процедуры.

Решение. Аргумент и результат функции – действительные числа, поэтому используем тип Real. В теле функции будет только оператор присваивания – для вычисления значения выражения. Процедура отличается строкой заголовка, - для передачи в основную программу результатов вычислений добавим параметр-переменную fx. Чтобы вывести результаты в виде таблицы, используем форматный вывод.

program proc_1;

function f (x: Real):Real;

begin     f:=2*cos(x)+3     end;

procedure proc_f (x: Real; var fx: real);

begin    fx:=2*cos(x)+3    end;

var x, fx: real;

begin

Writeln('с использованием процедуры:');

Writeln(' x f(x)');

x:=1; proc_f (x,fx);

Writeln (x:6:2, fx:6:2);

x:=4;

proc_f (x,fx); Writeln (x:6:2, fx:6:2);

x:=7.5;

 proc_f (x,fx); Writeln (x:6:2, fx:6:2);

 x:=20;

 proc_f (x,fx); Writeln (x:6:2, fx:6:2);

Readln;

Writeln('с использованием функции:');

Writeln(' x f(x)'); Writeln(1:6, f (1):6:2);

Writeln(4:6, f (4):6:2); Writeln(7.5:6:2, f (7.5):6:2);

Writeln(20:6, f (20):6:2); Readln;

end.

Пример 2. Создать рекурсивную функцию поиска i-го члена последовательности, заданной рекуррентной формулой A₁=const1, A₂=const2, A_i=3A_i-2-A_i-1. Вывести через пробел значения рекурсивной функции при значениях аргумента от 1 до 10 включительно.

Решение. По условию задачи аргумент может принимать только целые значения, поэтому функция имеет параметр-значение типа Integer. Выход из рекурсии в данном случае осуществляется при двух значениях аргумента (при i=1, i=2), поэтому в рекурсивной функции необходимы два вложенных условных оператора или же оператор выбора case. В приведенном примере использованы операторы if, но попробуйте самостоятельно записать решение с помощью оператора выбора. В основной программе значения аргумента - целые последовательные числа, поэтому следует воспользоваться оператором цикла с параметром for.

program proc_2; function A (i: Integer): Integer; beginif i=1 then A:=1 elseif i=2 then A:=3 else А:=3*A(i-2)-A(i-1) end; var i: Integer; beginfor i:=1 to 10 do Write (A(i),' '); Readln

end.

Задание к работе

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

Методические указания

Задачу необходимо решать согласно рассмотренной технологии:

1. Изучить словесную постановку задачи;
2. Сформулировать математическую постановку задачи;
3. Выбрать метод решения задачи, если это необходимо;
4. Разработать схему алгоритма;
5. Записать разработанный алгоритм на языке Паскаль;
6. Разработать контрольный тест программы;
7. Отладить программу;
8. Написать отчет.

Содержание отчета

1. Словесная постановка задачи.
2. Математическая формулировка задачи.
3. Схема алгоритма решения задачи.
4. Листинг программы.
5. Контрольный тест.
6. Результат тестирования программы.
7. Ответы на контрольные вопросы, задаваемые преподавателем.

 

Варианты заданий

Задание 1. Составить программу для решения задачи с применением функции пользователя.

1. Даны действительные числа s и t. Получить

g(1.2+s)+g(ts)–g(2s–t), где g(a)=

2. Даны действительные числа s и t. Получить f (t, -2s, 1.17) + f (2.2, t, s-t),

где f(a, b, c)=

3. Даны действительные числа s и t. Получить g(1.2, s) + g(t,s) - g(2s -1,st),

где g(a, b)=

.

4. Даны действительные числа s и t. Получить h(s, t) + h²(s -t, st) + h(1, 1),

где h(a,b)=

.

5. Вычислить u-f(0.5,a)+f(a,b)+f(a+b,a-b), используя функцию f(x,y)=
6. Даны действительные числа a, b. Получить и = min(a,b), v=min(ab, а+b), 
   w=min(u + v², 3.14).
7. Даны действительные числа х, у, z. Вычислить s =f(x,y) +f(x,z) +f(y,z), где f(a, b) =
8. Даны    действительное    число   х   и    целое    число    n.        Вычислить y=s(1, n)x² + s(n+1, 2n)x + s(1, 20), где s(a, b) = .
9. Даны два действительных числа х и у. Вычислить z=(sign х + sign y) sign(x+y),

где sign a =

 

Задание 2. Вывести значения рекурсивной функции при значениях аргумента от 1 до 10 включительно. 

1. Найти член последовательности, заданной формулой: D_i=7+D_i-1 при i>1, где D₁ определяется пользователем.
2. Найти член последовательности, заданной формулой: A_i=A_i-1-A_i-2 при i>2. Значения первого и второго членов последовательности вводятся пользователем.
3. Найти член последовательности, заданной следующим образом: y₁=0; y₂=10; y_n=2×y_n-1-y_n-2, где n>2.
4. Найти член последовательности, заданной формулой B_i=4·B_i-1, при i>1. Значения первого члена последовательности вводится пользователем.
5. Три точки заданы координатами (х1,у1), (х2,у2), (х3,у3). Выяснить, какие из них находятся на максимальном расстоянии друг от друга. Вывести значения этих расстояний.
6. Даны числа a,b,c,d. Вычислить Z=a+b+c+d, используя процедуру суммирования двух чисел.
7. Вычислить 2!+4!+6!+8!+10!.
8. Вычислить у=
1. . Определить значение Z=min(a,3b)*min(2a-b,2b). 
    
   Контрольные вопросы
1. Какой переменной присваивается значение в  функции?
2. Какие переменные в языке Паскаль называются локальными, а какие глобальными?
3. Какие  функции называют рекурсивными?
4. Как отличить «обычную» функцию от рекурсивной?
5. Если значения  функции являются операндами некоторого выражения, то которую из них можно вставить «непосредственно» в это выражение?