Программирование с использованием рекурсии

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

Программирование с использованием рекурсии

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

Цель работы: освоить способы программирования алгоритмов с использованием рекурсии.

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

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

Пример. Написать программу, содержащую подпрограммы, вычисляющий

с использованием и без использования рекурсии.

Решение

SUMIR;n: Integer; SUM:Real;

{------- Рекурсивная процедура-функция -------------}

Function S_REC(n:word):Real;n=1 then S_REC:=4S_REC:=S_REC(n-1)+(n+1)*(n+1)/n;

{------- Процедура-функция без рекурсии ------------}

Function S(n:word):Real;i: byte; Sum: Real;:=4;i:=2 to n do Sum:=Sum+(i+1)*(i+1)/i;:=Sum;

{----------- Рекурсивная процедура ----------------}

Procedure REC(n:word; Var S:Real);n=1 then S:=4Begin(n-1,S);:=S+(n+1)*(n+1)/n;

{------------ Процедура без рекурсии ------------}

Procedure SS(n:word; Var S:Real);i: byte;:=4;i:=2 to n do S:=S+(i+1)*(i+1)/i;;

{----------- Основная программа ----------------}

Begin

Write('n='); Readln(n);('Сумма равна');('1. Функция с рекурсией: ',S_REC(n):0:5);

REC(n,SUM);('3. Процедура c рекурсией: ',SUM:0:5);

SS(n,SUM);('4. Процедура без рекурсии: ',SUM:0:5);

End.

рекурсия алгоритм вычислительный

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

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

. В чем преимущества и недостатки использования рекурсии?

Задачи

Решить поставленные задачи различными способами: с применением рекурсии и без нее.

. Для заданного целого десятичного числа N получить его представление в p-ичной системе счисления (p<10).

. В упорядоченном массиве целых чисел ai, i=1...n найти номер элемента c используя метод двоичного поиска. Предполагается, что элемент c находится в массиве.

. Найти наибольший общий делитель чисел M и N. Используйте теорему Эйлера: Если M делится на N, то НОД (N, M)=N, иначе НОД (N, M)=

=НОД (M mod N, N).

. Вычислить число Фибоначчи Fb(n). Числа Фибоначчи определяются следующим образом: Fb(0)=1; Fb(1)=1; Fb(n)=Fb(n-1)+Fb(n-2).

. Найти значение функции Аккермана A(m, n), которая определяется для всех неотрицательных целых аргументов m и n следующим образом:

A(o, n)=n+1;(m, o)=A(m-1, 1); (m>o);(m, n)=A(m-1, A(m, n-1)); (m>o; n>o).

6. Вычислить m-ю производную полинома степени n

. Вычислить значение , используя рекуррентную формулу

в качестве начального приближения использовать значение x0=0.5(1+a).

. Найти максимальный элемент в массиве a1...an, используя очевидное соотношение max (a1...an)=max (max (a1...an-1), an).

. Вычислить .

. Вычислить

12. Вычислить произведение n³2 (n-четное) сомножителей

. Вычислить  по следующему алгоритму: , если N четное; , если N нечетное.

. Вычислить n!.

15. Выполнить сортировку массива целых чисел ai, i=1, n с помощью разделения (QuickSort). См. Вирт Н., Алгоритмы и структура данных.