Простыми словами о рекурсии
Содержание:
Рекурсивные обходы
Другим отличным применением рекурсии является рекурсивный обход.
Представьте, у нас есть компания. Структура персонала может быть представлена как объект:
Другими словами, в компании есть отделы.
-
Отдел может состоять из массива работников. Например, в отделе работают 2 сотрудника: Джон и Алиса.
-
Или отдел может быть разделён на подотделы, например, отдел состоит из подотделов: и . В каждом подотделе есть свой персонал.
-
Также возможно, что при росте подотдела он делится на подразделения (или команды).
Например, подотдел в будущем может быть разделён на команды и . И потенциально они могут быть разделены ещё. Этого нет на картинке, просто нужно иметь это в виду.
Теперь, допустим, нам нужна функция для получения суммы всех зарплат. Как мы можем это сделать?
Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл поверх объекта с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.
Давайте попробуем рекурсию.
Как мы видим, когда наша функция получает отдел для подсчёта суммы зарплат, есть два возможных случая:
- Либо это «простой» отдел с массивом – тогда мы сможем суммировать зарплаты в простом цикле.
- Или это объект с подотделами – тогда мы можем сделать рекурсивных вызовов, чтобы получить сумму для каждого из подотделов, и объединить результаты.
Случай (1), когда мы получили массив, является базой рекурсии, тривиальным случаем.
Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).
Алгоритм даже проще читается в виде кода:
Код краток и прост для понимания (надеюсь?). В этом сила рекурсии. Она работает на любом уровне вложенности отделов.
Схема вызовов:
Принцип прост: для объекта используются рекурсивные вызовы, а массивы являются «листьями» дерева рекурсии, они сразу дают результат.
Обратите внимание, что в коде используются возможности, о которых мы говорили ранее:
- Метод из главы Методы массивов для получения суммы элементов массива.
- Цикл для итерации по значениям объекта: возвращает массив значений.
Two ways of thinking
For something simple to start with – let’s write a function that raises to a natural power of . In other words, multiplies by itself times.
There are two ways to implement it.
-
Iterative thinking: the loop:
-
Recursive thinking: simplify the task and call self:
Please note how the recursive variant is fundamentally different.
When is called, the execution splits into two branches:
- If , then everything is trivial. It is called the base of recursion, because it immediately produces the obvious result: equals .
- Otherwise, we can represent as . In maths, one would write . This is called a recursive step: we transform the task into a simpler action (multiplication by ) and a simpler call of the same task ( with lower ). Next steps simplify it further and further until reaches .
We can also say that recursively calls itself till .
For example, to calculate the recursive variant does these steps:
So, the recursion reduces a function call to a simpler one, and then – to even more simpler, and so on, until the result becomes obvious.
Recursion is usually shorter
A recursive solution is usually shorter than an iterative one.
Here we can rewrite the same using the conditional operator instead of to make more terse and still very readable:
The maximal number of nested calls (including the first one) is called recursion depth. In our case, it will be exactly .
The maximal recursion depth is limited by JavaScript engine. We can rely on it being 10000, some engines allow more, but 100000 is probably out of limit for the majority of them. There are automatic optimizations that help alleviate this (“tail calls optimizations”), but they are not yet supported everywhere and work only in simple cases.
That limits the application of recursion, but it still remains very wide. There are many tasks where recursive way of thinking gives simpler code, easier to maintain.
Recursive structures
A recursive (recursively-defined) data structure is a structure that replicates itself in parts.
We’ve just seen it in the example of a company structure above.
A company department is:
- Either an array of people.
- Or an object with departments.
For web-developers there are much better-known examples: HTML and XML documents.
In the HTML document, an HTML-tag may contain a list of:
- Text pieces.
- HTML-comments.
- Other HTML-tags (that in turn may contain text pieces/comments or other tags etc).
That’s once again a recursive definition.
For better understanding, we’ll cover one more recursive structure named “Linked list” that might be a better alternative for arrays in some cases.
Imagine, we want to store an ordered list of objects.
The natural choice would be an array:
…But there’s a problem with arrays. The “delete element” and “insert element” operations are expensive. For instance, operation has to renumber all elements to make room for a new , and if the array is big, it takes time. Same with .
The only structural modifications that do not require mass-renumbering are those that operate with the end of array: . So an array can be quite slow for big queues, when we have to work with the beginning.
Alternatively, if we really need fast insertion/deletion, we can choose another data structure called a linked list.
The linked list element is recursively defined as an object with:
- .
- property referencing the next linked list element or if that’s the end.
For instance:
Graphical representation of the list:
An alternative code for creation:
Here we can even more clearly see that there are multiple objects, each one has the and pointing to the neighbour. The variable is the first object in the chain, so following pointers from it we can reach any element.
The list can be easily split into multiple parts and later joined back:
To join:
And surely we can insert or remove items in any place.
For instance, to prepend a new value, we need to update the head of the list:
To remove a value from the middle, change of the previous one:
We made jump over to value . The value is now excluded from the chain. If it’s not stored anywhere else, it will be automatically removed from the memory.
Unlike arrays, there’s no mass-renumbering, we can easily rearrange elements.
Naturally, lists are not always better than arrays. Otherwise everyone would use only lists.
The main drawback is that we can’t easily access an element by its number. In an array that’s easy: is a direct reference. But in the list we need to start from the first item and go times to get the Nth element.
…But we don’t always need such operations. For instance, when we need a queue or even a deque – the ordered structure that must allow very fast adding/removing elements from both ends, but access to its middle is not needed.
Lists can be enhanced:
- We can add property in addition to to reference the previous element, to move back easily.
- We can also add a variable named referencing the last element of the list (and update it when adding/removing elements from the end).
- …The data structure may vary according to our needs.
Глубина рекурсии
В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.
Два примера выше иллюстрируют именно этот случай. Правда в реальном мире, в отличие от мира математических абстракций, всегда есть какие-либо ограничения. Нельзя например бесконечно пересказывать одно и то же стихотворение, так как мы ограничены во времени.
Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны
Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.
Summary
Terms:
-
Recursion is a programming term that means calling a function from itself. Recursive functions can be used to solve tasks in elegant ways.
When a function calls itself, that’s called a recursion step. The basis of recursion is function arguments that make the task so simple that the function does not make further calls.
-
A recursively-defined data structure is a data structure that can be defined using itself.
For instance, the linked list can be defined as a data structure consisting of an object referencing a list (or null).
Trees like HTML elements tree or the department tree from this chapter are also naturally recursive: they branch and every branch can have other branches.
Recursive functions can be used to walk them as we’ve seen in the example.
Any recursive function can be rewritten into an iterative one. And that’s sometimes required to optimize stuff. But for many tasks a recursive solution is fast enough and easier to write and support.
Пары чисел
Что насчёт чего-нибудь более сложного, как, например, пар натуральных чисел с лексикографическим порядком?
Такой порядок можно определить, например, так:
Доказательство его фундированности предлагается читателю в качестве упражнения.
Ладно, шучу, мне просто лень описывать процесс разработки доказательства. Конечный результат будет выглядеть примерно так:
Можно заметить, что доказательство имеет примерно ту же структуру: мы рекурсивно вызываем нашу основную функцию в случае (так как мы стали меньше), а в остальных случаях мы рекурсивно вызываем нашу вспомогательную функцию .
Контрпримеры
Итак, мы встретились с парой типов и отношений на них, а также доказали их вполне упорядоченность. Но что случится, если мы попытаемся доказать что-то про фундированность отношения, которое таковым не является? Где именно и что именно сломается? Доказывать, что какие-то вещи невыразимы, бывает сложно, но мы попытаемся хотя бы немножко приблизиться к интуитивному пониманию этой самой невыразимости. Да и лично я считаю, что контрпримеры так же важны для понимания, как и обычные, положительные примеры, так что давайте ломать!
Плюсы и минусы рекурсивных функций
Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.
Плюсы:
Рекурсивный код снижает время выполнения функции.
Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.
В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия
И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.
Рекурсию легче отлаживать.
Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.
Минусы:
Рекурсивные функции занимают много места.
Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции.
Рекурсивные функции замедляют программу.
Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы или . Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам.
Рекурсия в поисковых системах
Да, именно так. Поисковым системам от рекурсии тоже некуда деваться. С тех пор, как был заведен обычай мерить авторитетность сайта (документа) количеством ссылок, поисковики попались в рекурсивную ловушку, и пусть они блуждают в ней вечно (это искреннее доброе пожелание автора). Ссылочный «вес» сайта складывается из маленьких кусочков «веса» от всех тех, которые на него ссылаются. Чтобы вычислить этот вес для A, на которого ссылаются B, C и D, надо обсчитать их вес, который в свою очередь передается всякими другими, вес которых тоже нужно обсчитывать… и так по всей учтенной в поисковике Сети. Совершенно рекурсивная задачка. А вы говорите — сплошная теория. Самая что ни на есть реальная практика.
Рекурсивный тИЦ от Яндекса
Яндексовский тИЦ устроен точно так же: A получает свою долю веса от B, чей вес точно так же нужно определить по весу ссылающихся на него… в общем, см. выше и не будем впадать в рекурсию повторяться. ТИЦ отличается от гугловского PageRank тем, что считается для сайтов в целом, а не для отдельных страниц. Поэтому Яндексу вроде бы живется полегче: сайтов все-таки на порядки меньше, чем страниц на них, так что пересчитать тИЦ — плевое дело в сравнении с пересчетом PageRank.
Однако тИЦ на выдачу не влияет. Для влияния на выдачу у Яндекса есть старательно спрятанный от оптимизаторских глаз ВИЦ, а это уже параметр страницы и аналог PageRank, так что считать Яндексу не пересчитать. Его счастье, что он пока обрабатывает только Россию и СНГ… да еще недавно в Турцию зачем-то полез. Но это же не вся планета — сколько там, в самом деле, той Турции…
Тест
Задание №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’;
}
|
1 |
#include <iostream> intfactorial(intn) { if(n<1) return1; else returnfactorial(n-1)*n; } intmain() { for(intcount=;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;
}
|
1 |
#include <iostream> intsumNumbers(intx) { if(x<10) returnx; else returnsumNumbers(x10)+x%10; } intmain() { 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);
}
|
1 |
#include <iostream> voidprintBinary(intx) { // Условие завершения if(x==) return; // Рекурсия к следующему биту printBinary(x2); // Выводим остаток (в обратном порядке) std::cout<<x%2; } intmain() { intx; 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 |
#include <iostream> voidprintBinaryDigits(unsignedintn) { // Условие завершения if(n==) return; printBinaryDigits(n2); std::cout<<n%2; } voidprintBinary(intn) { if(n==) std::cout<<‘0’;// выводим «0», если n == 0 else printBinaryDigits(static_cast<unsignedint>(n)); } intmain() { intx; std::cout<<«Enter an integer: «; std::cin>>x; printBinary(x); } |
The execution context and stack
Now let’s examine how recursive calls work. For that we’ll look under the hood of functions.
The information about the process of execution of a running function is stored in its execution context.
The is an internal data structure that contains details about the execution of a function: where the control flow is now, the current variables, the value of (we don’t use it here) and few other internal details.
One function call has exactly one execution context associated with it.
When a function makes a nested call, the following happens:
- The current function is paused.
- The execution context associated with it is remembered in a special data structure called execution context stack.
- The nested call executes.
- After it ends, the old execution context is retrieved from the stack, and the outer function is resumed from where it stopped.
Let’s see what happens during the call.
In the beginning of the call the execution context will store variables: , the execution flow is at line of the function.
We can sketch it as:
Context: { x: 2, n: 3, at line 1 }
pow(2, 3)
That’s when the function starts to execute. The condition is falsy, so the flow continues into the second branch of :
The variables are same, but the line changes, so the context is now:
Context: { x: 2, n: 3, at line 5 }
pow(2, 3)
To calculate , we need to make a subcall of with new arguments .
To do a nested call, JavaScript remembers the current execution context in the execution context stack.
Here we call the same function , but it absolutely doesn’t matter. The process is the same for all functions:
- The current context is “remembered” on top of the stack.
- The new context is created for the subcall.
- When the subcall is finished – the previous context is popped from the stack, and its execution continues.
Here’s the context stack when we entered the subcall :
-
Context: { x: 2, n: 2, at line 1 }
pow(2, 2) -
Context: { x: 2, n: 3, at line 5 }
pow(2, 3)
The new current execution context is on top (and bold), and previous remembered contexts are below.
When we finish the subcall – it is easy to resume the previous context, because it keeps both variables and the exact place of the code where it stopped.
Please note:
Here in the picture we use the word “line”, as in our example there’s only one subcall in line, but generally a single line of code may contain multiple subcalls, like .
So it would be more precise to say that the execution resumes “immediately after the subcall”.
The process repeats: a new subcall is made at line , now with arguments , .
A new execution context is created, the previous one is pushed on top of the stack:
-
Context: { x: 2, n: 1, at line 1 }
pow(2, 1) -
Context: { x: 2, n: 2, at line 5 }
pow(2, 2) -
Context: { x: 2, n: 3, at line 5 }
pow(2, 3)
There are 2 old contexts now and 1 currently running for .
During the execution of , unlike before, the condition is truthy, so the first branch of works:
There are no more nested calls, so the function finishes, returning .
As the function finishes, its execution context is not needed anymore, so it’s removed from the memory. The previous one is restored off the top of the stack:
-
Context: { x: 2, n: 2, at line 5 }
pow(2, 2) -
Context: { x: 2, n: 3, at line 5 }
pow(2, 3)
The execution of is resumed. It has the result of the subcall , so it also can finish the evaluation of , returning .
Then the previous context is restored:
Context: { x: 2, n: 3, at line 5 }
pow(2, 3)
When it finishes, we have a result of .
The recursion depth in this case was: 3.
As we can see from the illustrations above, recursion depth equals the maximal number of context in the stack.
Note the memory requirements. Contexts take memory. In our case, raising to the power of actually requires the memory for contexts, for all lower values of .
A loop-based algorithm is more memory-saving:
The iterative uses a single context changing and in the process. Its memory requirements are small, fixed and do not depend on .
Any recursion can be rewritten as a loop. The loop variant usually can be made more effective.
…But sometimes the rewrite is non-trivial, especially when function uses different recursive subcalls depending on conditions and merges their results or when the branching is more intricate. And the optimization may be unneeded and totally not worth the efforts.
Recursion can give a shorter code, easier to understand and support. Optimizations are not required in every place, mostly we need a good code, that’s why it’s used.
Вычисление сложного процента рекурсией и циклом FOR
Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:
- Срок кредита в годах
- Процентная ставка
- Количество платежей в год
- Сумма кредита
Формула расчёта сложного процента:
Так мы можем рассчитать всю сумму сразу. Но вместо этого, для расчёта мы используем цикл или рекурсию. В таком случае переменная времени (nt) будет обрабатываться в итерациях.
Давайте сразу создадим переменные, в которых будем хранить исходные числа и используем их в обоих методах:
Расчёт по сложной процентной ставке итеративно
Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.
Так выглядит код:
Единственное различие между этим и предыдущим примерами заключается в том, что мы делаем на несколько вычислений больше во время каждой итерации. Также увеличилось число итераций с 5 до 120.
Результат наших вычислений:
Расчёт по сложной процентной ставке рекурсивным способом
В предыдущем примере последовательность данных равна 120, что отражает количество раз, когда основная сумма пересчитывается. Цикл прерывается по завершении последовательности. Рекурсивный метод позволяет нам поступить схожим образом, т.е. инициализировать счётчик и задать два условия.
Условие 1: Счётчик не равен 0.
Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.
Условие 2: Счётчик равен 0
Возврат общей суммы
В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.
Здесь происходит тоже самое, только начальное значение теперь 120
Здесь мы либо снова вызываем функцию, либо возвращаем обновлённую общую сумму. Каждый раз вызывая функцию, значение счётчика уменьшается на 1. Возврат общей суммы происходит, когда счётчик равен 0.
По математике
Треугольник Серпинского -a ограничивается рекурсию из треугольников, образующих фрактал
Рекурсивно определенные множества
Пример: натуральные числа
Канонический пример рекурсивно определенного множества — это натуральные числа :
- 0 находится в N{\ Displaystyle \ mathbb {N}}
- если n находится в , то n + 1 находится вN{\ Displaystyle \ mathbb {N}}N{\ Displaystyle \ mathbb {N}}
- Набор натуральных чисел — это наименьший набор, удовлетворяющий двум предыдущим свойствам.
В математической логике аксиомы Пеано (или постулаты Пеано или аксиомы Дедекинда – Пеано) — это аксиомы для натуральных чисел, представленные в XIX веке немецким математиком Ричардом Дедекиндом и итальянским математиком Джузеппе Пеано . Аксиомы Пеано определяют натуральные числа, относящиеся к рекурсивной функции-преемнику, а также сложение и умножение как рекурсивные функции.
Пример: процедура доказательства
Другой интересный пример — это набор всех «доказуемых» предложений в аксиоматической системе , которые определены в терминах процедуры доказательства, которая индуктивно (или рекурсивно) определяется следующим образом:
- Если предложение является аксиомой, это доказуемое предложение.
- Если предложение может быть получено из истинно достижимых предложений с помощью правил вывода, это предложение доказуемо.
- Набор доказываемых предложений — это наименьший набор предложений, удовлетворяющих этим условиям.
Правила конечного деления
Правила конечного подразделения — это геометрическая форма рекурсии, которую можно использовать для создания фрактальных изображений. Правило подразделения начинается с набора полигонов, помеченных конечным числом меток, а затем каждый полигон подразделяется на меньшие помеченные полигоны способом, который зависит только от меток исходного многоугольника. Этот процесс можно повторять. Стандартная техника «средних третей» для создания множества Кантора — это правило подразделения, как и барицентрическое подразделение .
Функциональная рекурсия
Функция может быть рекурсивно определена в терминах самого по себе. Знакомый пример — последовательность чисел Фибоначчи : F ( n ) = F ( n — 1) + F ( n — 2). Чтобы такое определение было полезным, оно должно быть сведено к нерекурсивно определенным значениям: в этом случае F (0) = 0 и F (1) = 1.
Известной рекурсивной функцией является функция Аккермана , которая, в отличие от последовательности Фибоначчи, не может быть выражена без рекурсии.
Доказательства с использованием рекурсивных определений
Применение стандартной техники доказательства по случаям к рекурсивно определенным множествам или функциям, как в предыдущих разделах, дает структурную индукцию — мощное обобщение математической индукции, широко используемое для получения доказательств в математической логике и информатике.
Рекурсивная оптимизация
Динамическое программирование — это подход к оптимизации, который переформулирует задачу многопериодной или многоступенчатой оптимизации в рекурсивной форме. Ключевым результатом динамического программирования является уравнение Беллмана , которое записывает значение задачи оптимизации на более раннем этапе (или на более раннем этапе) в терминах его значения на более позднем этапе (или на более позднем этапе).
Теорема о рекурсии
В теории множеств это теорема, гарантирующая существование рекурсивно определенных функций. Для множества X , элемента a из X и функции f : X → X теорема утверждает, что существует единственная функция (где обозначает множество натуральных чисел, включая ноль) такая, что
FN→Икс{\ Displaystyle F: \ mathbb {N} \ to X}N{\ Displaystyle \ mathbb {N}}
- F()знак равноа{\ Displaystyle F (0) = а}
- F(п+1)знак равнож(F(п)){\ Displaystyle F (n + 1) = f (F (n))}
для любого натурального числа n .
Доказательство уникальности
Возьмем две функции и такие, что:
FN→Икс{\ Displaystyle F: \ mathbb {N} \ to X}гN→Икс{\ Displaystyle G: \ mathbb {N} \ to X}
- F()знак равноа{\ Displaystyle F (0) = а}
- г()знак равноа{\ Displaystyle G (0) = а}
- F(п+1)знак равнож(F(п)){\ Displaystyle F (n + 1) = f (F (n))}
- г(п+1)знак равнож(г(п)){\ Displaystyle G (п + 1) = е (G (п))}
где является элементом X .
Математической индукцией можно доказать, что F ( n ) = G ( n ) для всех натуральных чисел
n :
- Базовый случай : F (0) = a = G (0), поэтому равенство выполняется для n = 0 .
-
Индуктивный шаг : предположим, что F ( k ) = G ( k ) для некоторого . Тогда F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1) .
k∈N{\ Displaystyle к \ в \ mathbb {N}}- Следовательно, из F ( k ) = G ( k ) следует F ( k + 1) = G ( k + 1) .
По индукции F ( n ) = G ( n ) для всех .
п∈N{\ Displaystyle п \ в \ mathbb {N}}
Тривиальный тип
Пожалуй, самый простой пример — тип-синглтон с отношением, которое выполняется для любых двух элементов этого типа (тривиальным образом, так как у этого типа всего один элемент):
Давайте начнём писать доказательство фундированности:
Каков тип этой дырки?
Единственный способ создать значение типа — через конструктор :
Здесь — свидетель отношений между и . Но этот свидетель не даёт нам никакой новой информации, так как мы и так знаем, что любое значение связано с любым, поэтому мы можем его просто проигнорировать!
Какой тип дырки перед нами после этого?
Похоже, что мы пришли к тому, с чего начали: нам нужно произвести некоторый для , о котором мы ничего не знаем, и нам только остаётся ещё раз воспользоваться конструктором , передав в него ещё одну лямбду, и так до бесконечности. Понятно, что записать это не получится.
