Рекурсия? Что же это такое?, Помогите Опции

[Cheburashka]

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

[volvo]

Ну, еще не мешало бы сказать про особый тип рекурсии: хвостовую (правую) рекурсию, когда собственно рекурсивный вызов производится после всех остальных необходимых вычислений (у 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. Я сам везде, где можно стараюсь использовать именно этот способ. Возможно, и не поможет, но не помешает - точно. А если когда-нибудь используемый компилятор научится оптимизировать такое - то не надо будет переписывать код