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.

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

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

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

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

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


 

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

73816. Анализ устройств цифровой электроники на структурном уровне представления в системах моделирования VLSI-SIM и MODELSIM 2.26 MB
  Как видно из результатов моделирования схемы в VLSI-SIM и ModelSim, временные диаграммы совпадают. За исключением небольших скачков, которые наблюдались в VLSI-SIM, а в ModelSim они пропали.
73817. Изучение функционирования триггеров на моделях в системах VLSI_SIM и ModelSim 242 KB
  Как видно из результатов моделирования схемы в VLSI-SIM и ModelSim, временные диаграммы совпадают. Это говорит правильности составленной модели. При моделировании на поведенческом уровне на схеме отсутствуют задержки при переключении элементов.
73818. Учет денежных средств и расчетов 36.07 KB
  Счета раздела «Денежные средства» предназначены для обобщения информации о наличии и движении денежных средств в российской и иностранных валютах, находящихся в кассе, на расчетных, валютных и прочих счетах, открытых на территории РФ и за ее пределами, а также ценных бумаг и денежных документов.
73819. Учет основных средств и нематериальных активов 36.42 KB
  Понятие и классификация ОС и НМА ОС совокупность материально-вещественных ценностей используемых в качестве средств труда и действующих в течение длительного периода времени и утрачивающих свою стоимость по мере их использования в сфере материального производства и непроизводственной сфере. Оценка основных средств и НМА Во всех случаях независимо от ведомственной принадлежности форм собственности и видов деятельности применяется единый принцип оценки основных средств и НМА. В экономике различают 4 оценки ОС и НМА: аморти зация...
73820. Учет финансовых вложений. Понятие, классификация и оценка финансовых вложений 19.22 KB
  Для принятия к БУ активов в качестве ФВ необходимо единовременное выполнение следующих условий: Наличие надлежаще оформленных документов подтверждающих существование права у организации на ФВ и ан получение д с или др.активов вытекающее из этого права; Переход к организации фин.; Способность приносить организации экономические выгоды доход в будущем в форме процентов дивидендов либо прироста их стоимости в виде разницы между ценой продажи погашения ФВ его покупной стоимостью в результате его обмена использования при погашении...
73821. Учет труда и его оплаты 29.23 KB
  Учет труда и его оплаты Нормативная база Федеральный закон от 24 июля 2009 г. Виды формы и системы оплаты труда Существует основная и дополнительная оплата труда. Основная оплата труда оплата начисляемая работникам за отработанное время кол-во и качество выполненных работ; оплата по сдельным расценкам тарифным ставкам окладам премии сдельщикам и повременщикам доплаты в связи с отклонениями от нормальных условий работы за работу в ночное время за сверхурочные за бригадирство оплата простоев не по вине рабочих и т. Дополнительная...
73822. Учет затрат на производство продукции (работ, услуг) 73.5 KB
  Учет затрат на производство продукции работ услуг Нормативная база. Расходы обуславливаются затратами относимыми на себестоимость продукции работ услуг и выплатами из прибыли предприятия. Затраты характеризуют в денежном выражении объем ресурсов использованных в определенных целях и трансформируются в себестоимость продукции работ услуг.
73823. Проблемы обеспечения устойчивости каналов радиоуправления 48 KB
  Кроме систем связи институт разрабатывает автоматизированные системы управления и средства радио-противодействия как в интересах народного хозяйства так и силовых структур. В современных условиях безопасность страны и её граждан зависит не только от количества и качества ВВП приходящемся на душу населения вооружений которым обладают силовые структуры но и от качества системы управления которая состоит из органов управления командиров пунктов управления технических средств связи и средств автоматизированного управления. Создание АСУ...