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

[Cheburashka]

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

[Cheburashka]

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

[Lapp]

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

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

Факторил - замечательный пример.
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 и снова возвращает полученную шестерку - теперь уже тебе.

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

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