36298

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

Доклад

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

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

Русский

2013-09-21

23.5 KB

22 чел.

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

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

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

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.

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

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

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

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

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


 

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

4484. Довгострокові прогнози максимальних витрат води весняного водопілля 1.45 MB
  Довгострокові прогнози максимальних витрат води весняного водопілля Сучасний стан в області довгострокового прогнозування максимальних витрат води весняного водопілля Ще у 40-ві роки минулого сторіччя М.А. Великановим була запропонована для прогноз...
4485. Прогнози дат початку та проходження максимальних витрат води весняних водопіль на рівнинних річках 193.5 KB
  Прогнози дат початку та проходження максимальних витрат води весняних водопіль на рівнинних річках 1 Фізичні передумови та практичні прийоми прогнозів строків водопілля для окремих водозборів На відміну від прогнозів характеристик водного режиму вес...
4486. Довгострокові прогнози весняно-літнього водопілля гірських річок 370 KB
  Довгострокові прогнози весняно-літнього водопілля гірських річок Особливості формування водопілля гірських річок Довгострокові прогнози стоку річок базуються на знанні процесів накопичення й витрати вологи в річковому басейні, що зумовлюють характ...
4487. Довгострокові прогнози льодових явищ на основі характеристик атмосферних процесів 60 KB
  Довгострокові прогнози льодових явищ на основі характеристик атмосферних процесів 1 Фізичні основи та принципи прогнозів дат льодових явищ Строки льодових явищ на водних об’єктах залежать від масштабних атмосферних процесів, які розвиваються на...
4488. Набор учебных стендов для кабинета Правил Дорожного Движения 4.95 MB
  Введение Темой конструкторской разработки является создание учебных стендов для кабинета Правил Дорожного Движения. Эта работа содержит в себе 3 стенда: стенд макет автодрома, тренажер сигналы регулировщика и стенд сигналы светофора. Руководит...
4489. Предмет, мета та задачі курсу. Екологічні проблеми науково-технічного прогресу (НТП) 248.5 KB
  Предмет, мета та задачі курсу. Екологічні проблеми науково-технічного прогресу (НТП). Екологія – інтегральна міждисциплінарна наука. Основні положення загальної екології. Передумови виникнення екології як науки Протягом тривалого часу,...
4490. Ассемблер. Об ассемблере 24.38 KB
  Об ассемблере Интересно проследить, начиная со времени появления первых компьютеров и заканчивая сегодняшним днем, за трансформациями представлений о языке ассемблера у программистов. Когда-то ассемблер был языком, без знания которого нельзя было за...
4491. Программная модель микропроцессора 47.29 KB
  Программная модель микропроцессора На современном компьютерном рынке наблюдается большое разнообразие различных типов компьютеров. Поэтому возможно предположить возникновение у потребителя вопроса — как оценить возможности конкретного типа (или...
4492. Структура программы на ассемблере 80.09 KB
  Структура программы на ассемблере Программа на ассемблере представляет собой совокупность блоков памяти, называемых сегментами памяти. Программа может состоять из одного или нескольких таких блоков-сегментов. Каждый сегмент содержит совокупность пре...