Какова связь между рекурсией и доказательством по индукции?

Question

Какова связь между рекурсией и доказательством по индукции?

Скажем fn(n),

рекурсии fn(n) вызывает саму себя, пока не встречаются base condition;

индукция - это когда base condition встречается, попробуйте доказать, что (base case + 1) также верен.

Кажется, что рекурсия и индукция находятся в другом направлении. Один начинается с n по base case, другой начинается с base case по infinite.

Не могли бы кто-нибудь объяснить идею в деталях?

Answer 1

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

Помните, что из-за Curry-Howard correspondence типы предложений и программ являются доказательствами. Когда вы пишете функцию типа Nat -> Nat (я буду использовать нотацию Haskell), вы пытаетесь доказать, что, учитывая натуральное число, ваша программа завершится и произведет другое натуральное число. Теперь мы можем иметь определение так:

f 0 = 1 
f (1 + n) = n * f n 

, который является как рекурсивное определением f и индуктивное доказательство его прекращения в то же время!

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

Докажем, что е х оканчивается для любого х.

• Базовый чехол: у нас есть f 0 константа по определению, поэтому она завершается.
• Индуктивный корпус: если мы предположим, что f n завершает работу, f (1 + n) завершает работу (поскольку все функции, которые он вызывает, завершаются).

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

Теперь, чтобы ответить на вашу озабоченность по поводу «направления» рекурсии/индукции. Здесь полезно рассмотреть «направление спроса» и «направление поставок», которые противоположны.

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

Теперь, когда вы делаете индуктивные доказательства, теоремы являются вашим предложением, а цели - вашим требованием.Вы можете сделать теорему T 0 из базового случая, а затем улучшить, насколько бы вы ни старались использовать индуктивный случай: ваш источник питания от 0 до бесконечности. Теперь, если у вас есть цель G n, вы можете сделать из нее меньшие цели G (n-k), используя индуктивный шаг, пока не достигнете нуля. Таким образом, ваш спрос идет от n до 0.

Как вы можете видеть, направление поставок в обоих случаях «бесконечно», а направление спроса «равно нулю» в обоих случаях.

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

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

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