Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
(→Рекурсия) |
Admin (обсуждение | вклад) (→Рекурсия) |
||
Строка 15: | Строка 15: | ||
Примеры вычисления n!, a^n. | Примеры вычисления n!, a^n. | ||
− | |||
− | |||
Пример нахождения минимума в массиве. | Пример нахождения минимума в массиве. | ||
Строка 26: | Строка 24: | ||
Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка. | Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка. | ||
+ | |||
+ | Доказательство завершимости рекурсии | ||
+ | |||
+ | Формы рекурсивных подпрограмм | ||
+ | # Действия - на рекурсивном спуске | ||
+ | # Действия - на рекурсивном возврате | ||
+ | # Действия - на рекурсивном спуске и возврате | ||
+ | # Каскадная рекурсия | ||
+ | # Удаленная рекурсия: | ||
+ | function f(i: integer): integer; | ||
+ | begin | ||
+ | if B1(n) then Result:=... | ||
+ | else Result:=f(f(i-1)); | ||
+ | end; |
Версия 01:01, 17 марта 2009
Рекурсия
Определение рекурсии.
Рекурсивные определения. Примеры: n!, a^n. Нерекурсивная часть рекурсивного определения. Праворекурсивное и леворекурсивное определения.
Рекурсия в программировании. Прямая и косвенная рекурсия. Необходимость forward при косвенной рекурсии.
Простые примеры использования рекурсии. Рекурсивное зацикливание.
Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. Глубина рекурсии, текущий уровень рекурсии.
Примеры вычисления n!, a^n.
Пример нахождения минимума в массиве.
Замечания
- О переполнении программного стека
- О накладных расходах на рекурсию
- О замене рекурсии итерацией
Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка.
Доказательство завершимости рекурсии
Формы рекурсивных подпрограмм
- Действия - на рекурсивном спуске
- Действия - на рекурсивном возврате
- Действия - на рекурсивном спуске и возврате
- Каскадная рекурсия
- Удаленная рекурсия:
function f(i: integer): integer; begin if B1(n) then Result:=... else Result:=f(f(i-1)); end;