Рекурсия Опции

[Client]

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

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

[Gendalf]

Эта функция вычисляет факториал 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]

Я полностью согласен с Gendalf-ом но есть одно но . Если ты хочешь найти n! то тебе в главной программе надо написать такую строку

ans:=fact(n); writeln(ans);

где ans это ответ . Просто в такой программе ответ будет вычисляться с конца тоесть как отметил Gendalf fact(n):=n*(n-1)*(n-2)*...*3*2*1.

Сообщение отредактировано: Bard - 21.11.2007 3:29

[volvo]

Bard, а еще главная программа должна заканчиваться точкой, правда? Вопрос был - НЕ о том, как пользоваться функциями, а о том, как работает рекурсия. Тем более, что если я напишу:
WriteLn(Fact(n));
- то получу тот же ответ.

А, кстати, лучше делать не:

...
  fact := fact(i-1) * i
...

, а вот так:

...
  fact := i * fact(i - 1)
...

Строго говоря, при программировании на Паскале это не играет особой роли, но для как можно более безболезненного перехода на другие языки - привыкать желательно именно к такой форме записи, как я привел. Дело все в том, что есть компиляторы, оптимизирующие хвостовую рекурсию, только вот они первую форму записи не посчитают таковой. А вторую - да, посчитают, и подобная рекурсия развернется в итерацию...

[Lapp]

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

Да, это рекурсия. Общий принцип рекурсии рассказал 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]

Вопрос из теста: Какие из следующих описаний функции 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]

В первом случае она зависнет

Ничего подобного... В первом случае просто нет никакой рекурсии, вот и все. Посчитается значение 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 станет отрицательным. Дальше - см. комментарий ко второму фрагменту

В четвертом вроде все правильно

А вот в четвертом - как раз то, о чем я говорил - та самая хвостовая рекурсия. Вполне себе рабочая...