36298

Понятие рекурсии. Прямая и косвенная рекурсия

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-09-21

23.5 KB

19 чел.

Понятие рекурсии. Прямая и косвенная рекурсия.

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

Примером программы с использованием рекурсии может быть программа вычисления факториала числа. Факториал может быть определен рекурсивно:

n!= (n-1)!*n,   где n = 1, 2, 3,…

Пример. Программа, которая запрашивает ввод числа и затем выводит на экран значение факториала от него.

Var     k: integer;

Function  fakt (n: integer):longint;

 Begin

If n=1 then  fakt :=1

 Else fakt :=  fakt (n-1) *n;

  End;

 Begin

Writeln (‘ введите число ‘);

Readln (k);

Writeln (k, ‘ ! =  ‘,fakt(k));

  End.

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

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

При организации рекурсивной процедуры следует выполнять рекурсивный вызов по условию, которое на каком-то уровне рекурсии станет ложным.

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

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


 

А также другие работы, которые могут Вас заинтересовать

66888. Побудова розгорток паперових моделей будівлі засобами комп’ютерної графіки 647 KB
  Графіка – вид мистецтва, що включає малюнок і художнє зображення (походить від грецькі слова графо, що означає пишу, креслю, малюю). Комп’ютерна графіка – це галузь знань, що вивчає та розробляє методи і засоби синтезу, збереження й перетворення цифрових зображень за допомогою ЕОМ та інших технічних пристроїв.
66889. Базовые понятия цифровой электроники 215 KB
  К тому же поведение цифровых устройств всегда можно абсолютно точно рассчитать и предсказать. Однако у цифровых сигналов есть и крупный недостаток. Поэтому максимально достижимое быстродействие аналоговых устройств всегда принципиально больше чем цифровых.
66890. Программная инженерия в жизненном цикле программных средств 143 KB
  Первый класс составляют относительно небольшие программы создаваемые одиночками или небольшими коллективами 3 –5 специалистов которые: создаются преимущественно для получения конкретных результатов автоматизации научных исследований или для анализа относительно простых...
66891. ХРОНОЛОГИЧЕСКАЯ СПРАВКА 53 KB
  От 2 млн. лет назад Первые свидетельства протокультурной деятельности на Земле. Обработка камня и кости, использование примитивных орудий - начало каменного века. Полуживотное собирательство и охота. Естественные жилища - норы и пещеры.
66892. Принципы и понятия планирования 73 KB
  Планирование представляет собой особую форму деятельности направленную на разработку и обоснование программы экономического развития предприятия и его структурных звеньев на определенный календарный период в соответствии с целью его функционирования и ресурсным обеспечением.
66894. АСЕПТИКА 240.5 KB
  Знать: нормативные документы методы дезинфекции предстерилизационной очистки и стерилизации различных видов хирургических инструментов операционного белья перевязочного материала обработки операционного поля рук хирурга перед операцией. Определение асептики и антисептики понятие о дезинфекции и стерилизации...
66895. Грамматическое значение и грамматическая форма 124.5 KB
  Большинство слов в языке соотносится не с отдельными предметами, а с целым классами предметов, что обязательно предполагает их обобщение и абстрагирование от их индивидуальных признаков. Например, слово дерево соотносится с весьма разнообразными представителями соответствующего класса: тополь, береза, сосна, баобаб и т.д.
66896. Лексическое значение слова и понятие 111.5 KB
  Слово не является знаком каждого отдельного предмета, явления, признака. Трудно представить, как происходило бы общение, если бы каждый отдельный предмет имел собственное название. Человеческое мышление выделяет из множества явлений окружающей действительности...