Реферат: Рекурсия

👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.
Например, приведенное ниже определение двоичного кода является рекурсивным:
<двоичный код> ::= <двоичная цифра> | <двоичный код><двоичная цифра>
Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".
Вообще, в рекурсивном определении должно присуствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
Приведём другие примеры рекурсивных определений.
Пример 1. Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...*n. С другой стороны, Граничным условием в данном случае является n<=1.
Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n:
Задание. По аналогии определите функцию S(n), вычисляющую сумму цифр заданного натурального числа.
Пример 3. Функция C(m, n), где 0<=m<=n, для вычисления биномиального коэффициента по следующей формуле является рекурсивной.
Ниже будут приведены программные реализации всех этих (и не только) примеров.
Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.
Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновренно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
Выполнение действий в рекурсивной подпрограмме может быть организовано одним из вариантов:
рекурсивный подъём рекурсивный спуск и рекурсивный спуск, и рекурсивный подъём
Здесь P — рекурсивная подпрограмма. Как видно из рисунка, действия могут выполняться либо на одном из этапов рекурсивного обращения, либо на обоих сразу. Способ организации действий диктуется логикой разрабатываемого алгоритма.
Реализуем приведённые выше рекурсивные определения в виде функций и процедур на языке Pascal и в виде функций на языке C.
Function Factorial(N:integer):Extended;
Procedure Factorial(N:integer; Var F:Extended);
Else Begin Factorial(N-1, F); F:=F*N End
if (N<=1) F=1.; else F=Factorial(N-1)*N;
Procedure K(N:Longint; Var Kol:Byte)
Else Begin K(N Div 10, Kol); Kol:=Kol+1 End;
if (N<10) Kol=1; else Kol=K(N/10)+1;
Procedure C(m, n: Byte; Var R: Longint);
if (m==0||m==n) f=1; else f=C(m, n-1)+C(m-1, n-1);
Пример 4. Вычислить сумму элементов линейного массива.
При решении задачи используем следующее соображение: сумма равна нулю, если количество элементов равно нулю, и сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю.
Type LinMas = Array[1..100] Of Integer;
Function Summa(N : Byte; A: LinMas) : Integer;
If N = 0 Then Summa := 0 Else Summa := A[N] + Summa(N - 1, A)
Write('Количество элементов массива? '); ReadLn(N); Randomize;
A[I] := -10 + Random(21); Write(A[I] : 4)
WriteLn; WriteLn('Сумма: ', Summa(N, A))
printf("\nКоличество элементов массива? "); scanf("%d", &n);
printf("\nВ сформированном массиве %d чисел:\n", n);
{a[i]= -10+random(21); printf("%d ", a[i]);}
printf("Сумма: %d", summa(n-1, a));
if (N==0) return a[0]; else return a[N]+summa(N-1, a);
Пример 5. Определить, является ли заданная строка палиндромом, т.е. читается одинаково слева направо и справа налево.
Идея решения заключается в просмотре строки одновременно слева направо и справа налево и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Граничное условие — строка является палиндромом, если она пустая или состоит из одного символа.
Else Pal:= (S[1]=S[Length(S)]) and Pal(Copy(S, 2, Length(S) - 2));
Write('Введите строку: '); ReadLn(S);
If Pal(S) Then WriteLn('Строка является палиндромом')
Else WriteLn('Строка не является палиндромом')
printf("\nВведитестроку: "); gets(s);
if (pal(s)) printf("Строка является палиндромом");
else printf("Строка не является палиндромом");
Задание. Используя аналогичный подход, определите, является ли заданное натуральное число палиндромом.
Подводя итог, заметим, что использование рекурсии является красивым приёмом программирования. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике разумно заменять рекурсивные алгоритмы на итеративные.
Какое определение называется рекурсивным? Приведите собственные примеры рекурсивных определений.
Какой вспомогательный алгоритм (подпрограмма) называются рекурсивными? Приведите собственные примеры содержательных задач, где для решения может быть использован рекурсивный вспомогательный алгоритм.
Что такое граничное условие и каково его назначение в рекурсивной подпрограмме?
Что такое глубина рекурсии? Чему равна глубина рекурсии в приведённых выше примерах?
На каком этапе выполнения рекурсивной подпрограммы могут выполняться её операторы?
Почему приведённый ниже алгоритм посимвольного формирования строки завершится аварийно?
Write('Введите очередной символ: '); ReadLn(C);
На каком этапе выполняются действия в этом алгоритме?

Название: Рекурсия
Раздел: Рефераты по информатике, программированию
Тип: реферат
Добавлен 07:00:05 28 февраля 2008 Похожие работы
Просмотров: 521
Комментариев: 17
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Рекурсия
Курсовая работа: Основные законы регулирования внешнеэкономической деятельности РФ
Реферат: Развитие отечественной педагогики после 1917 года
Реферат по теме Компьютеризованная реклама
Мой Выбор Профессии Переводчик Сочинение
Самые Известные Эссе
Небольшое Сочинение На Тему Хлеб Всему Голова
Реферат На Тему Неотложные Состояния У Детей
100 Сочинений Для Школьников И Абитуриентов
Реферат по теме Классические модели стратегического анализа и планирования: модель ADL/LC
Дипломная работа: Удосконалення надання послуг в ресторані "Не гони"
Доклад по теме Экологический аудит водных ресурсов
Реферат: Sue The Dinosaur Essay Research Paper Sue
Реферат На Тему Реалізація Конституції
Реферат: Проблемы современной глобализации мировой экономики
Курсовая работа: Государство как публичное юридическое лицо во Франции
Символы Кузбасса Реферат
Риск И Его Разновидности Реферат
Контрольная Работа 1 По Геометрии 9
Реферат На Тему Reported Speech
Реферат: Взятие Барселоны 985
Реферат: Матильда Кшесинская (1872-1971)
Дипломная работа: Производство бетонных работ при строительстве гидротехниче-ских сооружений
Реферат: Учет денежных средств