36298

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

Доклад

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

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

Русский

2013-09-21

23.5 KB

32 чел.

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

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

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

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.

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

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

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

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

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


 

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

86124. Разработка и адаптация модели управления запасами на исследуемом предприятии 774.5 KB
  Объектом исследования данной работы стало предприятие, занимающееся торговлей продукцией. Основная задача состояла в разработке и адаптации системы управления запасами предприятия. В результате работы были изучены входные и выходные параметры модели управления запасами. Адаптирована данная модель на предприятии может быть при помощи разработанной программы, представляющей собой удобное и простое средство оптимизации управления запасами фирмы.
86125. Технічні засоби звукозапису авторського колективу 413 KB
  В даний час існує безліч клубів самодіяльної пісні в містах нашої країни проводиться велика кількість фестивалів і конкурсів присвячених цьому виду творчості. Наше завдання вибрати найбільш оптимальний варіант її еволюції забезпечити організацію АМСТ згодом і забезпечити спадкоємність творчості різних поколінь співаючих поетів. І було б невірним намагатися приписати створення перших зразків авторської творчості чевидно що це явище саме загальносвітове а не виключно вітчизняне. Самодіяльної творчості дуже часто досягнувши певного...
86126. Разработка системы прогнозирования необходимого количества специалистов с учетом выпускников школ, колледжа и лицеев 9.85 MB
  В работе рассматривается проблема разработки системы прогнозирования необходимого количества специалистов для потребностей предприятий. Приводимый в настоящей работе анализ развития региональной образовательной системы и рекомендации по их обоснованию основывающиеся в свою очередь на общих принципах...
86127. Разработка компьютеризированных системы моделирования и управление ценообразованием (на базе ГП ЛДЦ «Ультрамед») 1.81 MB
  В работе детально излагается ценовая политика предприятия, методы формирования цены на предприятии которые могут быть использованы для получения максимальной прибыли. А также в работе приведена структура документооборота, которая требует компьютерной поддержки, получена трендовая модель для прогнозирования...
86130. Блок сепаратора для исследования скважин. Расчет на прочность 72.66 MB
  Целью настоящего расчета является подтверждение прочности сепаратора для исследования скважин ПГМ 301.3012.00.000 при заданных в КД нагрузках и выбранных материалах. Расчет включает задачи, приведенные в содержании настоящего документа.