Рекурсивные алгоритмы (преимущества и недостатки)

Если пользователь ввел число больше единицы, то выполняется цикл, в теле которого на каждой итерации значение переменной factorial умножается на следующее натуральное число (переменную i).

Программа на языке  Паскаль:

Program fac;

Uses crt;

Var

factorial: longint;

n, i:byte;

Begin clrscr;

write(‘n=’);

readln (n);

factorial:=1;

for i:=2 to n do

factorial:=factorial*i;

writeln (‘n!=’, factorial);

readln;

end.

Числа Фибоначчи

Задача: Вывести на экран ряд чисел Фибоначчи, состоящий из n элементов.

Решение: Числа Фибоначчи – это элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, в которой каждое последующее число равно сумме двух предыдущих.

Описание переменных:

n – количество элементов ряда;

a, b – значения двух последних элементов ряда;

c – буферная («запасная») переменная;

i – счетчик.

 Алгоритм  решения задачи:

1. Получить значение n.
2. Присвоить a и b значения 0 и 1 соответственно (это первые числа ряда Фибоначчи). Вывести их на экран.

1. Выводить на экран сумму a и b;
2. Сохранить значение переменной b в c;
3. Записать в b сумму a и b;
4. Присвоить a значение с.

Программа на языке  Паскаль:

Program chisla;

Uses crt;

Var

a, b, c, i, n: integer;

begin clrscr;

write(‘n=’);

readln(n);

  a:=0;

write(a,’ ’);

b:=1;

write(b, ‘ ’);

for i:=3 to n do begin

write(a+b, ‘ ‘);

c:=b;

b:=a+b;

a:=c;

end;

readln

end.

 

ЗАКЛЮЧЕНИЕ

На основании  проведенного исследования можно сделать  несколько выводов:

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Баррон Д. Рекурсивные методы в программировании (Мир, 1974, 80 стр.).
2. Зуев Е.А. Turbo Pascal. Практическое программирование. – М.: Приор, 1997. – 336с.
3. Немнюгин С.А. Turbo Pascal: практикум – СПб.: Питер, 2001. – 256с.
4. Турбо Паскаль 7.0. Самоучитель. – СПб.: Питер; К.: Издательская группа BHV, 2002.
5. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие. Издание 7-е, переработанное. – М.: «Нолидж», 2000, - 416 с.
6. STUDLAB.COM  Рекурсия [электронный ресурс] http://studlab.com/news/rekursija/2011-05-31-109
7. Горлов А.В. Рекурсивные алгоритмы [электронный ресурс] http://otherreferats.allbest.ru/programming/00085599_0.html