пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

pogromirovanie:
» sooqa
Уася:
» History motherfuckers

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

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

Рекурсивной называется подпрограмма, в которой содержится обращение к самой себе. Такая рекурсия называется прямой. Есть также косвенная рекурсия, когда две или более подпрограмм вызывают друг друга. 
При обращении подпрограммы к самой себе происходит то же самое, что и при обращении к любой другой функции или процедуре: в стек записывается адрес возврата, резервируется место под локальные переменные, происходит передача параметров, после чего управление передается первому исполняемому оператору подпрограммы. 
Для завершения вычислений каждая рекурсивная подпрограмма должна содержать хотя бы одну ветвь алгоритма, заканчивающуюся возвратом в вызывающую программу. Простой пример рекурсивной функции - вычисление факториала. Чтобы получить значение факториала числа n, требуется умножить на n факториал числа (n - 1).Известно также, что 0! = 1 и 1! = 1. 
function fact(n : byte) : longint;
begin
if (n = 0) or (n = 1) then fact := 1 
else fact := n * fact(n - 1); 
end;
Рассмотрим, что происходит при вызове этой функции при n = 3. В стеке отводится место под параметр n, ему присваивается значение 3 и начинается выполнение функции. Условие в операторе if ложно, поэтому управление передается на ветвь else. Для вычисления выражения n * fact(n - 1) требуется повторно вызвать функцию fact. Для этого в стеке отводится новое место под параметр n, ему присваивается значение 2, и выполнение функции начинается сначала. В третий раз функция вызывается со значением параметра, равным 1, и вот тут-то становится истинным выражение (n = 0) or (n = 1), поэтому происходит возврат из подпрограммы в точку вызова, то есть на выражение n * fact(n - 1) для n = 2. Результат выражения присваивается имени функции и передается в точку ее вызова, то есть в то же выражение, только теперь происходит обращение к параметру n, равному 3. 
Достоинством рекурсии является компактная запись, а недостатками - расход времени и памяти на повторные вызовы функции и передачу ей параметров, а, главное, опасность переполнения стека. 


27.01.2014; 07:31
хиты: 190
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь