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.

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

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

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

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

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


 

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

66276. Хімічний та елементний склад живих організмів. Вода і мінеральні солі 63.5 KB
  Мета: ознайомити студентів з хімічним складом живих організмів, з біологічними елементами; розглянути їх біологічну роль в організмі. Розширити знання про біологічне значення в організмі неорганічних сполук води і мінеральних солей.
66277. Сигналы регулировщика 80 KB
  Цель: дать детям представление о работе регулировщика. Выучить сигналы регулировщика. Развивать внимание, мышление, память. Учить анализировать, обобщать, делать выводы. Обогащать активный словарный запас учащихся.
66278. Учись бути здоровим 457.5 KB
  Харчування дітей має бути різноманітним з достатньою кількістю вітамінів. Вітаміни корисні для людини. Слово вітаміни походить від латинського слова віта життя. Якщо вітамінів не вистачає людина важко хворіє.
66279. Англійська народна казка «Сорочаче гніздо» 46 KB
  Наша держава має добрих сусідів: росіян, білорусів, поляків, руминів. У новому розділі «Казки народів Європи» ми познайомимося з казками, які читають діти інших народів. Казки – це вигадані оповідання, котрі передаються протягом століть із роду в рід...
66280. Твоя країна – Україна. Символи держави. Розробка проекту «Славетні українці» 397.5 KB
  Мета: Дати уявлення про Україну як незалежну державу, про державну символіку; розширити і уточнити відомості про період козаччини; розвивати мовленнєву діяльність, уміння слухати своїх товаришів, робити аналіз сказаного...