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.

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

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

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

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

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


 

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

29690. Априорное знание, метафизика и объективность 36.5 KB
  Знание напротив характеризуется полной ясностью и свободно от ошибок Объектами мнений являются чувственные впечатления которые характеризуются нестабильностью. априорное знание предшествующее опыту и независимое от него. Априорное знание противоположно апостериорному эмпирическому знанию.
29691. Апостериорное (эмпирическое) знание и объективность 38.5 KB
  Одно из основных понятий теории познания. Эмпирические знания получают в результате применения эмпирических методов познания наблюдения измерения эксперимента. Это знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области.
29692. Категория как узловой пункт познания 35 KB
  Системный подход применяется к множествам объектов отдельным объектам и их компонентам а также к свойствам или интегральным характеристикам объектов. Границы применения системного подхода: 1 системный подход не самоцель плоды его четкие теоретические и экспериментальные выводы; 2 системный подход применим только к тем объектам которые обладают высокой степенью функциональной обособленности. Типы системного подхода: 1.
29697. Подходы к психологии как мультипарадигмальной науке 31.5 KB
  В этой дисциплине существует несколько парадигм естественнонаучный и гуманитарный соответствующих основным психологическим теориям таким как бихевиоризм когнитивизм и психоанализ и соответственно психология мультипарадигмальная наука. В настоящий момент в психологии различают два принципиально различных подхода: естественнонаучный и гуманитарный поскольку такие теории как бихевиоризм когнитивизм психоанализ и прочие суть именно теории пусть и глобальные а с парадигмой у них очень мало общего Естественнонаучный подход...