Версия для печати темы

Автор: Сергей Меркурьев 14.05.2009 18:07

Ну так вот на многих сайтах с задачами (не только acmp.ru) я находил такое определение, как рекурсия. Не могли бы Вы рассказать всё (ну что Вы знаете), что нужно юному программисту, для знания данной темы.

Автор: Ozzя 14.05.2009 18:14

Берется любой хороший учебник по Паскалю и читается.

Автор: Сергей Меркурьев 14.05.2009 18:16

А в учебнике "В.Б. Попова Turbo Pascal для школьников", там вроде нет(((

Автор: volvo 14.05.2009 18:19

В принципе, берется любой учебник по любому языку, и читается. Рекурсия - это не то, что доступно только в Паскале.

Начать можно http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F#.D0.A0.D0.B5.D0.BA.D1.83.D1.80.D1.81.D0.B8.D1.8F_.D0.B2_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B8. Ну, а потом - пробовать реализовать разные алгоритмы рекурсивно, чтоб понять, как оно работает.

Значит, бери другой учебник.

Автор: Ozzя 14.05.2009 18:19

В Фаронове есть.
http://pascal-books.narod.ru/books/faronov.zip

Автор: Сергей Меркурьев 14.05.2009 18:26

Ну я так понял что в основном рекурсия выполняетя с помощью подпрограмм (процедур и функций)?

Автор: Ozzя 14.05.2009 18:30

Ну да. Найдите какие-нибудь классичсекие примеры. Вычисление факториала, например.

Автор: Lapp 14.05.2009 20:02

Проще говоря, рекурсия - это когда подпрограмма (или функция) вызывается в ней самой. Ре-курс - буквально: повторный заход (как ре-монт - повторный монтаж).

Факторил - замечательный пример.
n! = 1*2*3*4..*(n-1)*n
- это его прямое определение.

А вот рекурсивное определение:
n! = (n-1)!*n
и
0!=1

Состаявляем функцию для его вычисления в соответствии с прямым определением:

function Fuctorial(n: integer): LongInt;
var
  i: integer;
  f: LongInt;
begin
  f:=1;
  for i:=1 to n do f:=f*i;
  Factorial:=f
end;

А вот функция, составленная рекуррентно:

function Fuctorial(n: integer): LongInt;
begin
  if n=0 then Factorial:=1 else Factorial:=n*Factorial(n-1)
end;

Вторая выглядит намного проще, согласись. Что происходит? Кога в нее заходишь, например, со значением n=3, она пытается умножить это значение на факториал двойки, который еще не знает. Она вызфывает функцию для вычисления этого факториала двойки, и уже та пытается 2 умножить на факториал 1. Снова то же самое: та вызывает факториал 0, чтобы вычислить факториал 1. И вот когда вызван факториал 0 - тогда происходит нечто другое: функция выходит со значением 1 в соответствии с первой частью условного оператора в ней.

А дальше разворачивается обратная цепочка. Вызов факториала 0 возвращает 1, домножает его на 1 и возвращает эту единицу экземпляру функции, который вызвал факториал 2. Та получает ее, домножает на 2 и возвращает. Следующий экземпляр функции получает эту двойку, домножает ее на 3 и снова возвращает полученную шестерку - теперь уже тебе.

Технически, происходит следующее. При каждом вызове функции всякий раз создается отдельная копия ее переменных, включая параметры. Именно с ними производятся действия, поэтому копии (экземпляры) функции они не мешают друг другу. При этом код (набор инструкций) только один.

Пример с факториалом - самый простой. Поиск по Форуму может дать тебе много интересных примеров)). Если будут трудности с поиском - пиши, я найду ченть.

Автор: volvo 14.05.2009 20:07

Олег даже тему открывал в свое время для интересных рекурсивных решений: http://forum.pascal.net.ru/index.php?s=&showtopic=1855&view=findpost&p=15510

Но что-то ее забросили. Андрей, если наткнешься на что-нибудь интересное, сохрани ссылку, потом добавим в ту тему, чтоб легче искать было...

Автор: Lapp 14.05.2009 20:45

Угу, я даже и не знал про нее((, до меня было. Конечно, можно даже специально поискать. Было много, заслуживающего внимания..

Добавлю по теме: несмотря на ее внешнюю привлекательность, использовать рекурсию нужно осторожно. Дело в том, что она очень сильно расходует ресурсы: как память, так и процессор. Все экземпляры живут в стеке. В 32-битных компиляторах его размер, как правило, достаточно большой, но в ТР/ВР это всего 64К. Можешь запустить многократный подсчет факториала и убедиться в этом сам. Там, где в прямой функции нужно всего лишь одно умножение (плюс один шаг цикла), то в рекурсивной вызов процедуры со всеми вытекающими..

Кстати не пытайся посчитать, скажем, факториал 30.. Это очень быстро растущая функция. Она вылетит по значению раньше, чем по ресурсам)).


Добавлено через 3 мин.
А чтобы наблюдать вылет по переполнению стека, можешь попытаться (кстати, для практики) реализовать функцию "вопросиал"))

n? = 0 + 1 + 2 + 3 + 4 + .. + (n-1) + n

Может, потребуется использовать LongInt

Автор: Сергей Меркурьев 14.05.2009 23:35

В общем то про факториал я знаю, и, что значение 30!, значение которого черезчур велико (265252859812191058636308480000000)... А вот про информацию Вам спасибо, к сожалению я ещё не приступил к изучению функций и процедур).

А вот не могли бы Вы сказать мне каким образом можно найти последнюю ненулевую цифры любого факториала??? Я попытался решить такую задачку сохраняя последние 6 цифр его, и последовательно удаляя все нули) Но вот только после значений Х>99 там уже начинаются проблемы)))

program metro;
  var N,F,R:longint;
begin
  assign (input,'input.txt');
  reset (input);
  assign (output,'output.txt');
  rewrite (output);
  Read (N);
  F:=1;
  R:=1;
  While R<=N do
    Begin
      F:=F*R;
      R:=R+1;
      If F mod 10=0 then Begin
                           F:=F div 10;
                           If F mod 10=0 then F:=F div 10
                         End;
      If F>999999 then F:=F mod 10;
    End;
  If F mod 10<>0 then Write (F mod 10)
                 else Write (F mod 10);
End.

Автор: Lapp 15.05.2009 0:00

Стоп! Это уже не теретический вопрос, как и не про рекурсию.
С предметом темы разобрался, вопросов больше нет?

Автор: Сергей Меркурьев 15.05.2009 0:01

В принципе если Вас не затруднит рассказать мне про подпрограммы (хотя я это и сам почитаю), тогда всё)

Автор: Lapp 15.05.2009 0:09

Нет проблем - спрашивай. Ты только пойми, что Форум требует организации. Это важно для тех, кто потом использует поиск. Хочешь про подпрограммы - открой тему про подпрограммы. Нельзя все валить в одну кучу, даже если и есть какая-то связь.
Про эту тему, про рекурсию - все?

Автор: Сергей Меркурьев 15.05.2009 0:11

В принципе про рекурсия да!

Автор: volvo 15.05.2009 14:27

Ну, еще не мешало бы сказать про особый тип рекурсии: хвостовую (правую) рекурсию, когда собственно рекурсивный вызов производится после всех остальных необходимых вычислений (у Lapp-а в посте №8 приведена именно такая реализация вычисления факториала). То есть, вот это:

function Factorial(n: integer): LongInt;
begin
  if n=0 then Factorial:=1 else Factorial:=Factorial(n-1)*n
end;

уже не хвостовая рекурсия, потому что рекурсивный вызов - не последний, после него есть еще вычисления... А разница - в том, что хвостовую рекурсию многие оптимизирующие компиляторы сводят к итерации, а значит, выполняться она будет быстрее и без доп. затрат памяти. Насчет Паскаль-компиляторов не знаю, чтоб кто-нибудь умел такое, но вот С++ компиляторы (в частности VC7+ от Microsoft, GCC из "GNU"-тых и ICC от Intel) прекрасно с данной задачей справляются.

Кстати, создатели FPC утверждают, что версия 2.2 тоже уже умеет оптимизировать хвостовую рекурсию, но надо будет проверить...

P.S. Я сам везде, где можно стараюсь использовать именно этот способ. Возможно, и не поможет, но не помешает - точно. А если когда-нибудь используемый компилятор научится оптимизировать такое - то не надо будет переписывать код