Программирование и рекурсия

Бесконечные цепи уникальных элементов

Если мы вернёмся к натуральным числам, но теперь рассмотрим отношение «быть больше, чем», то у нас тоже не получится доказать его фундированность. Неформально говоря, дело в том, что для любого наперёд заданного нам может быть дано число , большее, чем , для которого нужно предоставить свидетеля фундированности. Для этого тоже может быть дано третье число , большее, чем . Но проблема в том, что чисел, больших, чем , столько же, сколько чисел, больших чем , так что мы никак не сузили наше «целевое пространство»!

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

Или, в виде кода, кратко и ясно:

Так что либо ℕ не населено (что, очевидно, не так), либо не населён для любого .

Наконец-то рекурсия

Как же используется доказательство фундированности? Посмотрим ещё раз на функцию вычисления НОД:

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

Заключение

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

Кроме того, похожие фичи есть и в Idris в виде / и обёрток / для того самого случая размера как натурального числа. Да и, учитывая, что мы разобрали, как определяется и как работает , не составит труда определить самостоятельно соответствующий примитив в любом зависимо типизированном языке.

Тренировочные задачи на рекурсию

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

Задачи можно сдавать на языках C++ и Python, поэтому если вы хотите попрактиковаться в другом языке, то тоже можете сдавать задачи.

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

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

B: От A до B

Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если , или в порядке убывания в противном случае.

C: Функция Аккермана

В теории вычислимости важную роль играет функция Аккермана \(A(m, n)\), определенная следующим образом: \

Даны два целых неотрицательных числа \(m\) и \(n\), каждое в отдельной строке. Выведите \(A(m, n)\).

Рекурсия

Рекурсивная функция (или просто «рекурсия») в языке C++ — это функция, которая вызывает сама себя. Например:

#include <iostream>

void countOut(int count)
{
std::cout << «push » << count << ‘\n’;
countOut(count-1); // функция countOut() вызывает рекурсивно сама себя
}

int main()
{
countOut(4);

return 0;
}

При вызове функции countOut(4) на экран выведется , а затем вызывается countOut(3). countOut(3) выведет и вызывает countOut(2). Последовательность вызова countOut(n) других функций countOut(n-1) повторяется бесконечное количество раз (аналог бесконечного цикла). Попробуйте запустить у себя.

На уроке о стеке и куче в С++ мы узнали, что при каждом вызове функции, определенные данные помещаются в стек вызовов. Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека! Следовательно, в какой-то момент, память стека закончится и произойдет .

Плюсы и минусы рекурсивных функций

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

Плюсы:

Рекурсивный код снижает время выполнения функции.

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

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

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

Рекурсию легче отлаживать.

Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.

Минусы:

Рекурсивные функции занимают много места.

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

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

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

Литература

1. Многопоточный сервер Qt. Пул потоков. Паттерн Decorator – режим доступа: https://pro-prof.com/archives/1390. Дата обращения: 21.02.2015.
2. Джейсон Мак-Колм Смит Элементарные шаблоны проектирования : Пер. с англ. — М. : ООО “И.Д. Вильямс”, 2013. — 304 с.
3. Скиена С. Алгоритмы. Руководство по разработке.-2-е изд.: пер. с англ.-СПб.:БХВ-Петербург, 2011.-720с.: ил.
4. Васильев В. С. Анализ сложности алгоритмов. Примеры – режим доступа: https://pro-prof.com/archives/1660. Дата обращения: 21.02.2015.
5.  А.Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы, М., Вильямс, 2007.
6. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер ; пер. с англ. — М. : БИНОМ. Лаборатория знаний, 2006. — 406 с.
7. Сергиевский Г.М. Функциональное и логическое программирование : учеб. пособие для студентов высш. учеб. заведений / Г.М. Сергиевский, Н.Г. Волченков. — М.: Издательский центр «Академия», 2010.- 320с.
8. Книги по алгоритмам и структурам данных: – режим доступа: https://pro-prof.com/books-algorithms. Дата обращения: 21.02.2020.

Тест

Задание №1

Факториал целого числа N определяется как умножение всех чисел между 1 и N (0! = 1). Напишите рекурсивную функцию factorial(), которая возвращает факториал ввода. Протестируйте её с помощью первых 8 чисел.

Подсказка: Помните, что , поэтому умножение всех чисел между 1 и N — это то же самое, что и умножение всех чисел между N и 1.

Ответ №1

#include <iostream>

int factorial(int n)
{
if (n < 1)
return 1;
else
return factorial(n — 1) * n;
}

int main()
{
for (int count = 0; count < 8; ++count)
std::cout << factorial(count) << ‘\n’;
}

Задание №2

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

Ответ №2

#include <iostream>

int sumNumbers(int x)
{
if (x < 10)
return x;
else
return sumNumbers(x / 10) + x % 10;
}

int main()
{
std::cout << sumNumbers(83569) << std::endl;
}

Задание №3

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

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

Ответ №3

#include <iostream>

void printBinary(int x)
{
// Условие завершения
if (x == 0)
return;

// Рекурсия к следующему биту
printBinary(x / 2);

// Выводим остаток (в обратном порядке)
std::cout << x % 2;
}

int main()
{
int x;
std::cout << «Enter an integer: «;
std::cin >> x;

printBinary(x);
}

Задание №4

Используя программу из задания №3, обработайте случай, когда пользователь ввел или отрицательное число, например:

Подсказка: Вы можете конвертировать отрицательное целое число в положительное, используя для конвертации в unsigned int.

Ответ №4

#include <iostream>

void printBinaryDigits(unsigned int n)
{
// Условие завершения
if (n == 0)
return;

printBinaryDigits(n / 2);

std::cout << n % 2;
}

void printBinary(int n)
{
if (n == 0)
std::cout << ‘0’; // выводим «0», если n == 0
else
printBinaryDigits(static_cast<unsigned int>(n));
}

int main()
{
int x;
std::cout << «Enter an integer: «;
std::cin >> x;

printBinary(x);
}

Три случая применения рекурсии

Ещё одно знание, которое приобрёл в ходе учебных поисков. В каких случаях используется рекурсия? Рекурсию можно использовать в трёх случаях:

1. Для вывода последовательности чисел. Например, вывести на печать последовательность чисел из множества от 1 до 100.
2. Для вывода суммы чисел множества. Например, нужно вывести на печать сумму всех чисел от 1 до 30.
3. Для вывода произведения всех чисел того или иного множества. Например, вывести на печать перемноженные между собой числа от 1 до 50. Такая процедура имеет свое название — вычисление факториала.

Во всех этих случаях нужно сначала пройтись по последовательности чисел. Затем напечатать эту последовательность или вывести на печать их сумму или их произведение. Базовая операция — это пройтись по последовательности чисел, для чего собственно и вызывается рекурсия как повторение функции с изменением параметра (увеличение или уменьшение на 1 или на другое число). И дополнительная операция — сложение или умножение всех чисел множества.

Пары чисел

Что насчёт чего-нибудь более сложного, как, например, пар натуральных чисел с лексикографическим порядком?

Такой порядок можно определить, например, так:

Доказательство его фундированности предлагается читателю в качестве упражнения.

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

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

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

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

Рекурсия

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

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

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

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

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

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

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:

Рекурсия: Распечатать первые 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.

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

Хвостовая рекурсия и цикл

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

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

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

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

Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра , который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала: \(fact_n = n \cdot fact(n-1) \\ fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\ fact_n = factTail_{n, 1} \\ \\ factTail_{n, accumulator} = factTail(n-1, accumulator \cdot n)\\ factTail_{3, 1} = factTail_{2, 3} = factTail_{1, 6} = factTail_{0, 6} = 6 \)

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

начало; fibonacci(number)
вернуть fibonacci(number, 1, 1, 0)
конец

начало; fibonacci(number, iterator, fib1, fib2)
  если iterator == number вернуть fib1
  вернуть fibonacci(number, iterator + 1, fib1 + fib2, fib1)
конец

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

Опасности и подводные камни рекурсии

Рассмотрим простой пример.

<?php

// Пример бесконечной рекурсии

function foo(){
return foo();
}

foo();

?>

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

То же самое касается и примера со сложной рекурсией.

<?php

// Пример сложной бесконечной рекурсии

function foo(){
return bar();
}

function bar(){
return foo();
}

foo();

?>

В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно
приведёт к падению программы.

Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.

<?php

// Пример конечной рекурсии

function foo($n){
if($n < 1)
return;
return foo($n-1);
}

foo(100000);

?>

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

Рекурсия и ее виды[править]

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

• алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;
• рекурсивная функция — одно из математических уточнений интуитивного понятия вычислимой функции.

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

Виды рекурсииправить

Существуют следующие виды рекурсии:

Прямая рекурсияправить

Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.

В данном случае функция r1( ) вызывает саму себя.#include <iostream>using namespace std;void r1 (int a);void r2 (int a);void r3 (int a);void r1(int a){cout << «function r1» << endl;if (a < 6)r1(a+1);}int main ( ){r1 (0);return NULL;}

Косвенная рекурсияправить

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

В данном случае функция r1( ) вызывает функцию r2( ), которая вызывает r3( ).
Функция r3( ) в свою очередь снова вызывает r1( ).#include <iostream>using namespace std;void r1 (int a);void r2 (int a);void r3 (int a);void r1(int a);{cout <<< «function r1» << endl;if (a < 6)r2(a+1);}void r2(int a){cout << «function r2» << endl;if (a < 6)r3(a+1);}void r3(int a){cout << «function r3» << endl;if (a < 6)r1(a+1);}int main ( ){r1 (0);return NULL;}

Бесконечная рекурсияправить

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

Одна из самых больших опасностей рекурсии — бесконечный вызов функцией самой себя.
Например:void function (){function(); }
Другой пример:int Function (unsigned int n){// Unsigned int — тип, содержащий неотрицательные значенияif (n > 0){Function(n++);return n;}else return 0;}
При использовании подобных алгоритмов появляется ошибка, предупреждающая о переполнении стека. Причиной такой проблемы чаще всего является отсутствие базиса, либо других точек останова, так же неправильно заданные точки прерывания рекурсии

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

Альтернативы

Именованные функции

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

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

1, 2, 3, 4, 5map(function(n) {
     return (!(n > 1)) ? 1  arguments.callee(n-1) * n;
});

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

1, 2, 3, 4, 5map(function factorial(n) {
     return (!(n > 1)) ? 1  factorial(n-1) * n;
});

Передача функций в качестве аргументов

Даже без механизмов для ссылки на текущую функцию или вызывающую функцию анонимная рекурсия возможна на языке, который допускает функции в качестве аргументов. Это делается путем добавления другого параметра к базовой рекурсивной функции и использования этого параметра в качестве функции для рекурсивного вызова. Это создает функцию более высокого порядка, а сама передача этой функции позволяет анонимную рекурсию внутри фактической рекурсивной функции. Это можно сделать чисто анонимно, применив комбинатор с фиксированной точкой к этой функции более высокого порядка. Это в основном представляет академический интерес, особенно для того, чтобы показать, что лямбда-исчисление имеет рекурсию, поскольку результирующее выражение значительно сложнее, чем исходная именованная рекурсивная функция. И наоборот, использование комбинаторов с фиксированной точкой можно в общем называть «анонимной рекурсией», так как это заметное их использование, хотя у них есть и другие приложения.

Это показано ниже с использованием Python. Во-первых, стандартная именованная рекурсия:

def fact(n):
    if n == 
        return 1
    return n * fact(n - 1)

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

def fact0(n0):
    if n0 == 
        return 1
    return n0 * fact0(n0 - 1)
fact1 = lambda f, n1 1 if n1 ==  else n1 * f(n1 - 1)
fact = lambda n fact1(fact0, n)

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

fact1 = lambda f, n1 1 if n1 ==  else n1 * f(f, n1 - 1)
fact = lambda n fact1(fact1, n)

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

F = lambda f (lambda x f(f, x))
fact1 = lambda f, n1 1 if n1 ==  else n1 * f(f, n1 - 1)
fact = F(fact1)

Написано анонимно:

(lambda f (lambda x f(f, x))) \
(lambda g, n1 1 if n1 ==  else n1 * g(g, n1 - 1))

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

fact1 = lambda f (lambda n1 1 if n1 ==  else n1 * f(f)(n1 - 1))
fact = fact1(fact1)

Здесь есть две операции «применения функции высшего порядка к самой себе»: в первой строке и во второй. Разложение второго двойного приложения в комбинатор дает:

C = lambda x x(x)
fact1 = lambda f (lambda n1 1 if n1 ==  else n1 * f(f)(n1 - 1))
fact = C(fact1)

Без учета другого двойного внесения дает:

C = lambda x x(x)
D = lambda f (lambda x f(lambda v x(x)(v)))
fact1 = lambda g (lambda n1 1 if n1 ==  else n1 * g(n1 - 1))
fact = C(D(fact1))

Объединение двух комбинаторов в один дает комбинатор Y :

C = lambda x x(x)
D = lambda f (lambda x f(lambda v x(x)(v)))
Y = lambda y C(D(y))
fact1 = lambda g (lambda n1 1 if n1 ==  else n1 * g(n1 - 1))
fact = Y(fact1)

Расширение комбинатора Y дает:

Y = lambda f (lambda x f(lambda v x(x)(v))) \
              (lambda x f(lambda v x(x)(v)))
fact1 = lambda g (lambda n1 1 if n1 ==  else n1 * g(n1 - 1))
fact = Y(fact1)

Их объединение дает рекурсивное определение факториала в лямбда-исчислении (анонимные функции одной переменной):

(lambda f (lambda x f(lambda v x(x)(v)))
           (lambda x f(lambda v x(x)(v)))) \
(lambda g (lambda n1 1 if n1 ==  else n1 * g(n1 - 1)))