Форум «Всё о Паскале» _ Теоретические вопросы _ Рекурсия
Автор: Client 21.11.2007 0:33
Function fact(i:integer):longint; begin if (i=0) or (i=1) then fact:=1 else fact:=fact(i-1)*i end;
Объясните, пожалуйста, как она работает (ведь это рекурсия?)
Автор: Gendalf 21.11.2007 2:47
Эта функция вычисляет факториал i! Если i=1 или 0, то факториал равен 1. если нет, то он вычисляет значение факториала (i-1), предварительно умножив его на i Так он спускается, пока не дойдет до i=1. в итоге если в начальной процедуре i=4, то факториал будет иметь вид fact=4*fact(3)=4*3*Fact(2)=4*3*2*fact(1)=4*3*2*1=4!
Автор: Bard 21.11.2007 3:28
Я полностью согласен с Gendalf-ом но есть одно но . Если ты хочешь найти n! то тебе в главной программе надо написать такую строку
ans:=fact(n); writeln(ans);
где ans это ответ . Просто в такой программе ответ будет вычисляться с конца тоесть как отметил Gendalf fact(n):=n*(n-1)*(n-2)*...*3*2*1.
Автор: volvo 21.11.2007 4:06
Bard, а еще главная программа должна заканчиваться точкой, правда? Вопрос был - НЕ о том, как пользоваться функциями, а о том, как работает рекурсия. Тем более, что если я напишу: WriteLn(Fact(n)); - то получу тот же ответ.
А, кстати, лучше делать не:
... fact := fact(i-1) * i ...
, а вот так:
... fact := i * fact(i - 1) ...
Строго говоря, при программировании на Паскале это не играет особой роли, но для как можно более безболезненного перехода на другие языки - привыкать желательно именно к такой форме записи, как я привел. Дело все в том, что есть компиляторы, оптимизирующие хвостовую рекурсию, только вот они первую форму записи не посчитают таковой. А вторую - да, посчитают, и подобная рекурсия развернется в итерацию...
Автор: Lapp 21.11.2007 14:36
Цитата(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 (про хвостовую рекурсию) - это оптимизация работы рекурсии. Она возможна не всегда, но если компилятор все же может с уверенностью распознать ее, то он, грубо говоря, заменяет рекурсиивный вызов на цикл. Это дает существенную экономию памяти и времени выполнения при сохранении простоты программного текста. Но ты сначала добейся полной ясностью с главным принципом, а потом уже разбирайся с оптимизациями (если захочешь )
Автор: Client 21.11.2007 23:57
Вопрос из теста: Какие из следующих описаний функции f(n), каторая должна вычислять факторил от n правильны? а)
function f(n:integer):integer; begin f:=n*(n-1) end;
б)
function f(n:integer):integer; begin if n=0 then f:=1 else f:=f(n+1)-(n+1) end;
в)
function f(n:integer):integer; begin if n=0 then f:=1 else f:=n*(n-1)*f(n-2) end;
г)
function f(n:integer):integer; begin if n=0 then f:=1 else f:=n*f(n-1) end;
В первом случае она зависнет Во втором вроде тоже зависнет, т.к. N не уменьшется и вызывается все время f(1) В третьем посчитает неправильно, допустим n=5,то 5*4*f(3)*f(1), здесь пропустится f(2) В четвертом вроде все правильно Скажите, пожалуйста, где я ошибся
Автор: volvo 22.11.2007 1:04
Цитата
В первом случае она зависнет
Ничего подобного... В первом случае просто нет никакой рекурсии, вот и все. Посчитается значение N*(N-1), а не факториал (на тройке не проверять, там ответ случайно совпадет с ожидаемым), но ничего не зависнет...
Цитата
Во втором вроде тоже зависнет, т.к. N не уменьшется и вызывается все время f(1)
Не зависнет, а вылетит с переполнением стека. Потому что условием выхода из рекурсии является N = 0, а N все время увеличивается. Теоретически, выполнение могла бы завершиться, как пример - см. сюда:
var n: integer; begin n := 2; while N <> 0 do begin writeln(n); inc(n); end; end.
Эта программа не зависает, а заканчивает работу, пройдя по всему диапазону положительных и отрицательных чисел, на с рекурсией - дело другое. Там стек закончится быстрее, поэтому будет Stack Overflow...
Цитата
В третьем посчитает неправильно, допустим n=5,то 5*4*f(3)*f(1), здесь пропустится f(2)
В третьем - выдаст правильный ответ, если переданное изначально значение N - четное, и вылетит с переполнением, если N - нечетное. Все дело в том, что рекурсивный вызов - F = n*(n - 1)*F(n-2), следовательно в случае четного аргумента функция "попадет" на граничное значение, равное нулю, которое прекратит рекурсию, а в случае нечетного - "перескочит" его и N станет отрицательным. Дальше - см. комментарий ко второму фрагменту
Цитата
В четвертом вроде все правильно
А вот в четвертом - как раз то, о чем я говорил - та самая хвостовая рекурсия. Вполне себе рабочая...