Эти два понятия связаны с понятиями индукция и рекурсия .Обе эти концепции являются способами описания бесконечно больших семейств объектов, хотя они различаются по своему подходу.
Когда вы определяете что-то снизу вверх , вы определяете это индуктивно .Идея состоит в том, что вы начинаете с набора фиксированных элементов и способа объединения этих элементов в новые элементы.В приведенном выше определении снизу вверх первоначально единственным элементом в наборе из всего списка целых чисел является пустой список.У вас также есть правило, которое позволяет вам взять список из набора целых чисел и превратить его во что-то на один шаг больше, добавив целое число.
Когда вы определяете что-то сверху вниз, вы определяете его рекурсивно .Идея состоит в том, что вы начинаете с некоторого очень большого семейства объектов - в данном случае, каждого возможного списка - и затем описываете только те списки, которые состоят исключительно из целых чисел.Обычно элементы, определенные совместно, определяются путем взятия существующих объектов и исключения из объектов, которые не совпадают.Например, в примере со списками целых чисел вы определяете, является ли что-то списком целых чисел, беря любой список, который вам нравится, и затем проверяя, что, если вы продолжаете разбивать его вниз, вниз и вниз, вы в конечном итоге получаете некоторые объекты, которыеВы знаете, это списки целых чисел (в данном случае просто пустой список).
Эти две формы фактически эквивалентны друг другу, но они служат различным целям.Индукция пытается собрать весь набор допустимых объектов, затем определяет все объекты, соответствующие описанию.Первоначально рекурсия ничего не определяет, но затем проверяет, соответствует ли какой-либо объект, который у вас есть, некоторым критериям, разбивая его на части и проверяя.Из-за магического способа, которым эти два математически определены, любое индуктивное определение может быть превращено в рекурсивное определение и наоборот (при условии, что все объекты, о которых вы говорите, конечны).
РЕДАКТИРОВАТЬ : Если вы действительно готовы к увлекательной поездке, вы можете проверить связанные понятия Coinduction и Corecursion .Это математический двойник индукции и рекурсии, обеспечивающий совершенно иной способ мышления относительно определения структуры данных.В частности, они допускают бесконечно большие структуры данных , которые обычно не могут быть определены индуктивно.Интересно, что существует связь между коиндукцией, corecursion, индукцией и рекурсией в терминах фиксированных точек .Вы можете думать об индуктивном определении структуры данных как о наименьшем наборе, соответствующем некоторому свойству, тогда как коиндуктивное определение является наибольшим набором с этим свойством.Это действительно круто!