Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями

Версия 01:05, 17 марта 2009

Рекурсия

Определение рекурсии.

Рекурсивные определения. Примеры: n!, a^n. Нерекурсивная часть рекурсивного определения. Праворекурсивное и леворекурсивное определения.

Рекурсия в программировании. Прямая и косвенная рекурсия. Необходимость forward при косвенной рекурсии.

Простые примеры использования рекурсии. Рекурсивное зацикливание.

Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. Глубина рекурсии, текущий уровень рекурсии.

Примеры вычисления n!, a^n.

Пример нахождения минимума в массиве.

Замечания

• О переполнении программного стека
• О накладных расходах на рекурсию
• О замене рекурсии итерацией

Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка.

Доказательство завершимости рекурсии

Формы рекурсивных подпрограмм

1. Действия - на рекурсивном спуске
2. Действия - на рекурсивном возврате
3. Действия - на рекурсивном спуске и возврате
4. Каскадная рекурсия
5. Удаленная рекурсия:

function f(i: integer): integer;
begin
  if B1(n) then Result:=...
  else Result:=f(f(i-1));
end;

Пр. Функция Аккермана.

A(n,m) = m+1, n=0;
A(n,m) = A(n-1,1), n>0, m=0;
A(n,m) = A(n-1,A(n,m-1)), n>0, m>0.

Пример плохого использования рекурсии - числа Фибоначчи Исправление ситуации - вспомогательный массив

Пример хорошего использования рекурсии - ханойские башни.

Замена рекурсии итерацией с использованием стека