Модуль: Подпрограммы. Рекурсия


Задача

1/12

Рекурсия. Что это?

Теория Нажмите, чтобы прочитать/скрыть

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

Если вспомнить математику, то там можно встретить принцип математической индукции. Он заключается в следующем: некоторое утверждение справедливо для всякого натурального n, если
    1) оно справедливо для n = 1;
    2) из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.

В программировании этот прием называют рекурсией.

Рекурсия - это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.

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

void Rec(int a)
{
  if (a>0) { Rec(a-1); }
  Console.WriteLine(a);
}

Схематично работу рекурсии можно изобразить блок-схемой.

 
Процедура Rec() выполняется с параметром 3. Затем в внутри процедуры с параметром 3 вызывается процедура с параметром 2 и т.д., пока не произойдет вызов процедуры с параметром 0. При вызове процедуры с параметром 0 рекурсивного вызова уже не произойдет и процедура с параметром 0 напечатает число 0 и закончит работу. Затем управление передается обратно в процедуру с параметром 1, она также заканчивает свою работу печатает число 1 и т.д. до процедуры с параметром 3. 

Все вызвавшиеся процедуры хранятся в памяти, до тех пор пока не закончат свою работу. Количество одновременно работающих процедур называется глубиной рекурсии.

Задача

Используя разобранную процедуру, добавьте в основной программе необходимые строки.
Разберитесь, почему программа выдает такой ответ.