IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

> Рекурсия
сообщение
Сообщение #1


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


Function fact(i:integer):longint;
begin
if (i=0) or (i=1) then
fact:=1
else
fact:=fact(i-1)*i
end;

Объясните, пожалуйста, как она работает (ведь это рекурсия?)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Client @ 20.11.2007 20:33) *

Объясните, пожалуйста, как она работает (ведь это рекурсия?)

Да, это рекурсия. Общий принцип рекурсии рассказал Gendalf. Я попробую сказать, как он работает в Паскале.

Ты знаешь, что программа есть код + данные? Когда ты запускаешь программу, она создает в памяти одну копию КОДА подпрограммы Fact. А в момент ОБРАЩЕНИЯ к ней всякий раз в памяти выделяется участок для ее данных.

Допустим теперь, ты вызываешь: Fact(3)
При этом по запросу программы операционная система выделяет в памяти облать для размещения всех переменных этой программы (объявленных + формальные параметры). Потом формальным параметрам присваиваются нужные значения (в нашем примере - тройка). Затем управление передается на ту область памяти, где лежит код, и программа начинает работать. В данном случае она смотрит, что i не равно 1, вычитает из трех один, получает 2 - и вызывает Fact(2). При этом происходит все то же самое: система выделяет память, передается формальный параметр (2).. Заметь - это уже ДРУГАЯ область памяти. Поэтому двойка не затрет ту тройку. Снова передастся управление на ТУ ЖЕ самую область кода, но теперь она работает уже с другими адресами памяти (точка выхода из программы запомнится в стеке). Из 2 вычтется 1, получится 1, и вызовется Fact(1).

Снова выделится еще одна область данных (теперь их уже три), и в нее запишется 1. Управление перейдет на все тот же код (снова точка выхода из программы запомнится в стеке), но теперь уже на операторе if выполнение пойдет по другой ветви (поскольку i=1). Произойдет выход из этой функции с присвоением ей значения 1, при этом вся область данных выделенная последней, третья, освобождается. Управление вернется на сохраненный в стеке адрес. По этому адресу лежит что? Там лежит умножение результата функции на значение формального параметра в этой копии (то есть 2). 1*2=2. Снова выход из функции с присвоением ей значения 2 и освобождением второй области данных и переход на сохраненное значение адреса. Там 2 умножается на 3 и результат (6) присваивается функции. Выход из функции, освобождение первой области данных.

Получается, что при вычислении, например, 10! потребуется 10 раз выделить область памяти под данные при одной области памяти с кодом. Поскольку факториал растет очень быстро, то его величина выйдет за границы допустимого раньше, чем кончится память. Но в других задачах (с мало изменяющимся значением и большой областью данных) может случиться, что при работе рекурсии память будет исчерпана. В TP/BP память, в которой выделяется место для данных (стек) ограничена 64КБ, так что рекурсией надо пользоваться с оглядкой..

То, что сказал volvo (про хвостовую рекурсию) - это оптимизация работы рекурсии. Она возможна не всегда, но если компилятор все же может с уверенностью распознать ее, то он, грубо говоря, заменяет рекурсиивный вызов на цикл. Это дает существенную экономию памяти и времени выполнения при сохранении простоты программного текста. Но ты сначала добейся полной ясностью с главным принципом, а потом уже разбирайся с оптимизациями (если захочешь smile.gif)


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 7:42
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name