Что такое рекурсия

На языке

Лингвист Ноам Хомский , среди многих других, утверждал, что отсутствие верхней границы количества грамматических предложений в языке и отсутствие верхней границы грамматической длины предложения (помимо практических ограничений, таких как время, доступное для произнесения одного ), можно объяснить как следствие рекурсии на естественном языке.

Это можно понять в терминах рекурсивного определения синтаксической категории, например предложения. Предложение может иметь структуру, в которой после глагола следует другое предложение: Дороти думает, что ведьмы опасны , в котором фраза « Ведьмы опасны» встречается в более крупном. Таким образом, предложение может быть определено рекурсивно (очень грубо) как нечто со структурой, которая включает словосочетание, глагол и, возможно, другое предложение. На самом деле это просто частный случай математического определения рекурсии.

Это обеспечивает способ понимания творчества языка-неограниченного числа грамматических предложений, потому что сразу же предсказывает , что предложения могут быть произвольной длины: Дороти считает , что Toto подозревает , что Железный человек сказал , что … . Помимо предложений, существует множество структур, которые можно определить рекурсивно, и, следовательно, множество способов, которыми предложение может встраивать экземпляры одной категории в другую. За прошедшие годы языки в целом оказались поддающимися такому анализу.

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

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

Рекурсивная грамматика формальная грамматика , которая содержит рекурсивные правила производства .

Рекурсивный юмор

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

Рекурсия, см. Рекурсия .

Вариант можно найти на странице 269 в указателе некоторых изданий книги Брайана Кернигана и Денниса Ричи « Язык программирования C» ; запись индекса рекурсивно ссылается на себя («рекурсия 86, 139, 141, 182, 202, 269»). Ранние версии этой шутки можно найти в «Let’s talk Lisp» Лорана Сиклоши (опубликовано Prentice Hall PTR 1 декабря 1975 г. с датой авторских прав 1976 г.) и в «Software Tools» Кернигана и Плагера (опубликовано Addison- Wesley Professional 11 января 1976 г.). Шутка также появляется в «Среде программирования UNIX» Кернигана и Пайка. Он не появился в первом издании Языка программирования C . Эта шутка является частью фольклора функционального программирования и была широко распространена в сообществе функционального программирования еще до публикации вышеупомянутых книг.

Другая шутка заключается в том, что «Чтобы понять рекурсию, вы должны понимать рекурсию». В англоязычной версии поисковой системы Google при поиске по запросу «рекурсия» сайт предлагает «Возможно, вы имели в виду: рекурсия ». Альтернативная форма — это от Эндрю Плоткина : «Если вы уже знаете, что такое рекурсия, просто запомните ответ. В противном случае найдите кого-нибудь, кто стоит ближе к Дугласу Хофштадтеру, чем вы; затем спросите его или ее, что такое рекурсия».

Рекурсивные акронимы — еще один пример рекурсивного юмора. PHP , например, означает «PHP-препроцессор гипертекста», WINE означает «WINE не является эмулятором». GNU означает «GNU не Unix», а SPARQL означает «протокол SPARQL и язык запросов RDF».

В лингвистике

См. также: Рекурсия (лингвистика)

В лингвистике рекурсией называют способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь» может быть за счёт рекурсии расширено как «Ваня догадался, что кошка съела мышь», далее как «Катя знает, что Ваня догадался, что кошка съела мышь» и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку. Однако в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Дэниэл Эверетт (англ.).

В математике

См. также: Рекурсивная функция

Треугольник Серпинского

В математике рекурсия имеет отношение к методу определения функций и числовых рядов: рекурсивно заданная функция определяет своё значение через обращение к себе самой с другими аргументами. При этом возможно два варианта:

  • Конечная рекурсивная функция. Она задаётся таким образом, чтобы для любого конечного аргумента за конечное число рекурсивных обращений привести к одному из отдельно определённых частных случаев, вычисляемых без рекурсии. Классический пример: рекурсивно-определённый факториал целого неотрицательного числа: n!={n⋅(n−1)!,n>1,n={\displaystyle n!={\begin{cases}n\cdot (n-1)!,&n>0\\1,&n=0\end{cases}}}. Здесь каждое следующее рекурсивное обращение делается с аргументом, меньшим на единицу. Поскольку n, по определению, целое неотрицательное число, через n рекурсивных обращений вычисление функции гарантированно придёт к частному случаю !=1{\displaystyle 0!=1}, на котором рекурсия прекратится. Таким образом, несмотря на рекурсивность определения, вычисление функции для любого аргумента из области определения окажется конечным.
  • Бесконечная рекурсивная функция. Она задаётся в виде обращения к самой себе во всех случаях (по крайней мере, для некоторых из аргументов). Подобным образом могут задаваться бесконечные ряды, бесконечные непрерывные дроби и так далее. Практическое вычисление точного значения здесь, естественно, невозможно, поскольку потребует бесконечного времени. Требуемый результат находится аналитическими методами. Тем не менее, если речь идёт не о получении абсолютно точного значения, а о вычислении заданного приближения искомого значения, то тут в некоторых случаях возможно прямое использование рекурсивного определения: вычисления по нему ведутся до тех пор, пока необходимая точность не будет достигнута. Примером может служить разложение в непрерывную дробь числа e:
e=2+22+33+44+…=2+f(2){\displaystyle e=2+{\cfrac {2}{2+{\cfrac {3}{3+{\cfrac {4}{4+\ldots }}}}}}\;=2+f(2)}, где f(n)=nn+f(n+1){\displaystyle f(n)={\cfrac {n}{n+f(n+1)}}}
Прямой расчёт по приведённой формуле вызовет бесконечную рекурсию, но можно доказать, что значение f(n) при возрастании n стремится к единице (поэтому, несмотря на бесконечность ряда, значение числа Эйлера конечно). Для приближённого вычисления значения e достаточно искусственно ограничить глубину рекурсии некоторым наперёд заданным числом и по достижении его использовать вместо f(n){\displaystyle f(n)} единицу.

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

С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.

В математике отдельно рассматривается класс так называемых «примитивно рекурсивных» функций. Определение примитивно рекурсивной функции также рекурсивно, оно задаёт набор примитивных функций и набор правил; функция является примитивно рекурсивной, если она может быть представлена как комбинация примитивно рекурсивных функций, образованная по этим правилам.

Примеры рекурсии в математике:

  • Метод Гаусса — Жордана для решения систем линейных алгебраических уравнений является рекурсивным.
  • Уже упоминавшийся факториал целого неотрицательного числа.
  • Числа Фибоначчи определяются с помощью рекуррентного соотношения:

    Первое и второе числа Фибоначчи равны 1
    Для n>2{\displaystyle n>2}, n{\displaystyle n}-e число Фибоначчи равно сумме (n−1){\displaystyle (n-1)}-го и (n−2){\displaystyle (n-2)}-го чисел Фибоначчи
  • Практически все геометрические фракталы задаются в форме бесконечной рекурсии (например, треугольник Серпинского).
  • Стандартный пример вычислимой рекурсивной функции, не являющейся примитивно рекурсивной — функция Аккермана: для неотрицательных целых чисел m{\displaystyle m} и n{\displaystyle n} следующим образом:
A(m,n)={n+1,m=;A(m−1,1),m>,n=;A(m−1,A(m,n−1)),m>,n>{\displaystyle A(m,\;n)={\begin{cases}n+1,&m=0;\\A(m-1,\;1),&m>0,\;n=0;\\A(m-1,\;A(m,\;n-1)),&m>0,\;n>0.\end{cases}}}

Расчет факториалов

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

Так, в соответствии с этим определением, мы имеем . Напомним также, что значение определяется равным , а факториалы отрицательных чисел не определены.

В следующем примере показано, как подсчитать факториалы итерационно, т. е. с помощью цикла , в котором вычисляется результат:

Выполнить код »
Скрыть результаты

Этот пример можно легко преобразовать в рекурсию. Внимательнее изучив формулу факториала, мы можем прийти к выводу, что:

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

Для того, чтобы окончательно разорвать замкнутый круг дополним рекурсивное определение еще одним, которое будет служить для остановки процесса:

Попробуем теперь вычислить значение 5!, несколько раз применив правило и однократно правило :

Вместо вычисления значения с помощью цикла можно просто снова вызвать функцию , передав ей очередное меньшее значение. Рекурсия останавливается, когда значение становится равным 1:

Выполнить код »
Скрыть результаты

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

А теперь давайте разберём как же работает наша функция .

Когда вызывается с аргументом 1, функция возвращает 1. В противном случае она возвращает произведение . Для вычисления этого значения вызывается с num — 1. Это происходит, пока num не станет равно 1.

Например, при передаче числа 5, у нас образуется следующая цепочка вызовов:

Ничего не умножается, пока мы спускаемся к базовому случаю . Затем мы начинаем подниматься обратно, по одному шагу.

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

Общее количество вложенных вызовов называют глубиной рекурсии. В случае с , всего будет num вызовов. Максимальная глубина рекурсии в браузерах ограничена 10 000 рекурсивных вызовов.

Когда функция вызывает сама себя, в стеке выделяется место для хранения новых копий локальных переменных и параметров. Код функции работает с данными переменными. Большое количество рекурсивных вызовов в функции может привести к переполнению стека. Если это произойдет, то возникнет ошибка — переполнение стека.

Рекурсия

Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия.

Рекурсивностью в Паскале могут обладать как функции, так и процедуры.

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

Поэтому важно: На каждом шаге выполнения рекурсивного тела процедуры или функции обязательно либо изменение параметра данной функции, либо наличие условия, при котором она больше себя не будет вызывать!

Рассмотрим простой пример использования рекурсивной процедуры:

Пример: Напечатать последовательность чисел в обратном порядке, используя рекурсивный вызов процедуры. Например:
Из условия задачи ясно, что условием завершения рекурсии будет сам аргумент функции, который следует уменьшать на единицу, пока он .

1
2
3
4
5
6
7
8
9
10
procedure row(ninteger);
begin
     if n >=1 then begin
        write (n, ' ');
        row(n-1)
     end;
end;
begin
    row(10);
end.

Теперь рассмотрим более сложный пример использования рекурсии в Паскаль.

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

Например: при переданном функции числе , должно в итоге вернуть
Использовать операции .

1
2
3
4
5
6
7
8
9
10
procedure reverse (n integer);
  begin
       write (n mod 10);
       if (n div 10) <>  then
         reverse(n div 10)
  end;
  begin
  writeln;
  reverse(3078);
  end.

Рекурсия: Распечатать последовательность, используя рекурсию:

А теперь посмотрим, как используется рекурсия при вычислении факториала в Паскаль.

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

Подсказка:
Выводим формулу

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var x integer;
   function fact (a integer) integer;
   begin
        if (a<=1) then
          a=1
        else
          a=a*(fact(a-1));
   fact=a;
end;
begin
writeln('Число?');
readln(x);
writeln(fact(x));
end.

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

Рекурсия: Написать рекурсивную функцию определения степени числа.

Дополните код:

1
2
3
4
5
6
7
8
9
10
11
12
13
var x,y integer;
function stepen (a,b integer)integer;
var ...
begin
  ...
end;
begin
  writeln('число?');
  readln(x);
  writeln('степень?');
  readln(y);
  writeln(stepen(x,y));
end.

Рекурсия: Необходимо сымитировать работу цикла . Выводить каждый раз слово «привет» и значение счетчика. Для этого использовать переменную счетчика шагов, которую нужно реализовать, как параметр процедуры. Второй параметр – общее количество шагов (количество итераций цикла).

Дополните код:

1
2
3
4
5
6
7
8
procedure LoopFor(i, n integer);
{Первый параметр – счетчик шагов, второй параметр – общее количество шагов}
begin
  ...                     
end;
begin
  LoopFor(1,10);                    
end.

Рекурсия: Найти НОД методом Евклида (алгоритм Евклида). Использовать рекурсивную процедуру.

Для чисел 3430 и 1365:

остаток от деления 3430 на 1365 3430 mod 1365 = 700
остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток 1365 mod 700 = 665
остаток также не нуль, поэтому еще одно деление 700 mod 665 = 35
остаток также не нуль, поэтому еще одно деление 665 mod 35 = 0
остаток нуль НОД равен 35

Рекурсия: Распечатать первые 10 чисел Фибоначчи (до 21), используя рекурсивную процедуру с двумя параметрами.
Результат должен быть:
Дополните код:

1
2
3
4
5
6
7
8
9
procedure fib (i,n integer);
  begin
       writeln (i+n,' ');
       if ... then
           fib(...,...)
  end;
begin
  fib(,1);
end.

Потренируйтесь в решении задач по теме, щелкнув по пиктограмме:

Напутствие

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

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

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

На этом всё, спасибо за внимание. Перевод статьи Tom Grigg: Recursive Programming

Перевод статьи Tom Grigg: Recursive Programming

Области применения рекурсии

Рекурсия является очень мощным инструментом программирования. Ее можно использовать для решения задач, которые более эффективно представляются рекурсией и могут использовать стек вызовов. Как правило, это относится к задачам сортировки, которые эффективно решаются с помощью рекурсии, обеспечивающей более высокую скорость, чем циклы.

В задаче, получившей название Ханойская башня, даны три стрежня и диски разного размера, которые в исходном состоянии надеты на первый стержень в виде башни. Задача состоит в том, чтобы перенести башню на другой стержень, при этом запрещается класть большой диск на маленький. Эту замечательную задачу можно легко решить с помощью рекурсии за 2n — 1 ходов, где n — число дисков.

Например, возьмем четыре диска и попытаемся перенести их со стержня A на стержень C, используя стержень B для временного хранения. С помощью описанной ниже рекурсивной функции это может быть выполнено за 15 ходов. Процесс решения можно визуализировать этим апплетом. Функция вызывается (2n * 2) – 1, или 31 раз. Причина, по которой число вызовов функции не равно числу ходов, кроется в том, что для обработки ходов необходимо установить стек вызовов. В этом примере используется головная рекурсия (листинг 4).

Листинг 4. Листинг 4
private  static void solveTower(int num, int fromPeg, int toPeg,
			int tempPeg) {
 		if (num > 0) {
 			// move a disc from the fromPeg to the tempPeg
			solveTower(num - 1, fromPeg, tempPeg, toPeg);

 			System.out.println("Disc moved from " + fromPeg + " to " + toPeg);

 			// move disc from the tempPeg to the toPeg
			solveTower(num - 1, tempPeg, toPeg, fromPeg);
		}
	}

Результат для четырех дисков показан в листинге 5.

Листинг 5. Листинг 5
1. Диск перенесен с 1 на 2
2. Диск перенесен с 1 на 3
3. Диск перенесен с 2 на 3
4. Диск перенесен с 1 на 2
5. Диск перенесен с 3 на 1
6. Диск перенесен с 3 на 2
7. Диск перенесен с 1 на 2
8. Диск перенесен с 1 на 3
9. Диск перенесен с 2 на 3
10. Диск перенесен с 2 на 1
11. Диск перенесен с 3 на 1
12. Диск перенесен с 2 на 3
13. Диск перенесен с 1 на 2
14. Диск перенесен с 1 на 3
15. Диск перенесен с 2 на 3

Ханойская башня — широко распространённая задача, которую можно решить с помощью рекурсии. Однако не все задачи столь очевидны, многие из них требуют времени на анализ и решение. Ханойскую башню можно решить и с помощью циклов, однако это потребует использования нескольких различных циклов и итераторов. Это решение будет работать дольше и потребует большего объема кода.

Ниже показан итерационный способ решения Ханойской башни. В этом примере использованы операции с битами, которые работают быстрей математических операций. За основу была взята эта программа на языке C.

Листинг 6. Листинг 6
int  numMoves = (1 << numDiscs) - 1;
int [] pegs = { 1, 2, 3, 1, 3, 2 };
int  count = 0;
		
for  (int currMove=1; currMove <= numMoves; currMove++) {
	int disc = 0;
 	while ( (currMove >> disc & 1) == 0 ) {  
		disc++;
	}
 	int level=(numDiscs - disc) & 1;  
 	int fromPeg =(currMove >> ++disc) % 3;
	fromPeg = pegs;
 	int toPeg =(fromPeg + level) % 3 + 1 ;
 	System.out.println (++count + ". Disc moved from " + fromPeg  + " to " + toPeg) ;
}

Контрольные примеры

Приведенные ниже контрольные примеры запускались в 64-разрядной среде исполнения IBM Java Runtime Environment (JRE) 7.0.4.0 (с аргументом командной строки -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable=no). Чтобы среда исполнения не тратила время на расширение и сжатие кучи, JRE запускалась с фиксированным размером кучи 256 МБ. Отключение API Attach не позволяет JRE запускать приложения-агенты (обычно используемые для мониторинга), что нормализует производительность в каждом тесте. При увеличении стека вызовов для инициализации стека и поддержания его на уровне 3 МБ использовался аргумент командной строки -Xss3m -Xssi3m.

Вычисление суммы

При суммировании чисел цикл показал значительно более высокую производительность, а концевая рекурсия оказалась быстрее головной. При увеличении стека вызовов Java до 3 МБ головная рекурсия сравнялась по скорости с концевой, но все же не смогла догнать цикл.

Рисунок 1. Рисунок 1. Вычисление суммы

Вычисление факториала

Этот примечательный пример иллюстрирует зависимость результатов от используемых операторов. При использовании простого типа данных int лучшие результаты во всех случаях получились для цикла. Применение типа int ограничивает величину результата до 32-разрядного целого числа со знаком. Для больших факториалов можно использовать тип данных BigInteger, но такая конструкция будет более затратной. Результаты применения BigInteger показали, что использование головной рекурсии в паре с концевой обеспечивает лучшее быстродействие, чем чисто концевая рекурсия или цикл.

Вычисление сложного процента рекурсией и циклом FOR

Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:

  1. Срок кредита в годах
  2. Процентная ставка
  3. Количество платежей в год
  4. Сумма кредита

Формула расчёта сложного процента:

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

Давайте сразу создадим переменные, в которых будем хранить исходные числа и используем их в обоих методах:

Расчёт по сложной процентной ставке итеративно

Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.

Так выглядит код:

Единственное различие между этим и предыдущим примерами заключается в том, что мы делаем на несколько вычислений больше во время каждой итерации. Также увеличилось число итераций с 5 до 120.

Результат наших вычислений:

Расчёт по сложной процентной ставке рекурсивным способом

В предыдущем примере последовательность данных равна 120, что отражает количество раз, когда основная сумма пересчитывается. Цикл прерывается по завершении последовательности. Рекурсивный метод позволяет нам поступить схожим образом, т.е. инициализировать счётчик и задать два условия.

Условие 1: Счётчик не равен 0.

Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.

Условие 2: Счётчик равен 0

Возврат общей суммы

В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.

Здесь происходит тоже самое, только начальное значение теперь 120

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

Теоремы[править]

Теорема о примитивной рекурсивности вычислимых функцийправить

Теорема:
Если для вычислимой функции существует примитивно рекурсивная функция , такая что для любых аргументов максимальное количество шагов, за которое будет посчитана на МТ равно , то примитивно рекурсивная функция.
Доказательство:

Каждому состоянию МТ поставим в соответствие список из четырех чисел , где:

L — состояние МТ слева от головки ленты, представлено в виде числа в системы счисления с основанием равным алфавиту МТ. Младшие разряды находятся возле головки. Пробелу соответствует ноль, чтобы число было конечным.

R — состояние МТ справа от головки, представлено аналогично L только возле головки МТ находятся старшие разряды.

S — номер текущего состояния.

C — символ на который указывает головка ленты.

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

Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их и .

Рассмотрим функцию двух аргументов которая принимает состояние МТ , число шагов и возвращает состояние МТ после шагов.
Покажем что — примитивно рекурсивная функция.

, где

Вместо подставим и в итоге получим что — примитивно рекурсивная функция.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector