Если вы строите минимальное количество операций обычного компьютера с нуля, «Итерация» стоит на первом месте в качестве строительного блока и требует меньше ресурсов, чем «рекурсия», следовательно, это быстрее.
Мы создадим иерархию понятий, начиная с нуля и определяя в первую очередь базовые, основные понятия, затем строим понятия второго уровня с ними и т. Д.
Первая концепция: Ячейки памяти, память, состояние . Чтобы сделать что-то, вам нужно мест для хранения окончательных и промежуточных значений результатов. Давайте предположим, что у нас есть бесконечный массив «целочисленных» ячеек, называемых Memory , M [0..Infinite].
Инструкции: сделать что-то - преобразовать ячейку, изменить ее значение. изменить состояние . Каждая интересная инструкция выполняет преобразование. Основные инструкции:
а) Установка и перемещение ячеек памяти
- сохранить значение в памяти, например: сохранить 5 м [4]
- скопировать значение в другую позицию: например: сохранить m [4] m [8]
b) Логика и арифметика
- и, или, xor, не
- add, sub, mul, div. например добавьте m [7] m [8]
Исполнительный агент : ядро в современном процессоре. «Агент» - это то, что может выполнять инструкции. Агент также может быть человеком, следующим алгоритму на бумаге.
Порядок шагов: последовательность инструкций : т. Е. Делать это сначала, делать это после и т. Д. Обязательная последовательность инструкций. Даже одна строка выражений является «обязательной последовательностью инструкций». Если у вас есть выражение с определенным «порядком оценки», то у вас есть шагов . Это означает, что даже одно составное выражение имеет неявные «шаги», а также имеет неявную локальную переменную (назовем это «результатом»). e.g.:
4 + 3 * 2 - 5
(- (+ (* 3 2) 4 ) 5)
(sub (add (mul 3 2) 4 ) 5)
Выражение выше подразумевает 3 шага с неявной переменной «result».
// pseudocode
1. result = (mul 3 2)
2. result = (add 4 result)
3. result = (sub result 5)
Таким образом, даже инфиксные выражения, поскольку у вас есть определенный порядок вычисления, являются обязательной последовательностью инструкций . Выражение подразумевает последовательность операций, которые должны быть выполнены в определенном порядке, и поскольку имеется шагов , существует также неявная промежуточная переменная «result».
Указатель инструкций : Если у вас есть последовательность шагов, у вас также есть неявный «указатель инструкций». Указатель инструкции отмечает следующую инструкцию и продвигается после чтения инструкции, но до ее выполнения.
В этой псевдо-вычислительной машине указатель инструкций является частью Памяти . (Примечание: обычно Указатель инструкций будет «специальным регистром» в ядре ЦП, но здесь мы упростим концепции и предположим, что все данные (включая регистры) являются частью «Памяти») *
Прыжок - Если у вас есть заказанное количество шагов и Указатель инструкций , вы можете применить инструкцию " store ", чтобы изменить значение самого указателя инструкции. Мы назовем это конкретное использование инструкции store с новым именем: Jump . Мы используем новое имя, потому что его проще воспринимать как новую концепцию. Изменяя указатель инструкций, мы инструктируем агента «перейти к шагу x».
Infiniт. е. итерация : с помощью прыжка назад теперь вы можете заставить агента «повторять» определенное количество шагов. На данный момент у нас есть бесконечная итерация.
1. mov 1000 m[30]
2. sub m[30] 1
3. jmp-to 2 // infinite loop
Условное - Условное выполнение инструкций. С помощью «условного» предложения вы можете условно выполнить одну из нескольких инструкций в зависимости от текущего состояния (которое можно установить с помощью предыдущей инструкции).
Правильная итерация : Теперь с условным предложением мы можем избежать бесконечного цикла инструкции jump back . Теперь у нас есть условный цикл и затем правильная итерация
1. mov 1000 m[30]
2. sub m[30] 1
3. (if not-zero) jump 2 // jump only if the previous
// sub instruction did not result in 0
// this loop will be repeated 1000 times
// here we have proper ***iteration***, a conditional loop.
Именование : присвоение имен определенной ячейке памяти с данными или удержание шага . Это просто "удобство", чтобы иметь. Мы не добавляем никаких новых инструкций, имея возможность определять «имена» для областей памяти. «Наименование» - это не инструкция для агента, а просто удобство для нас. Именование делает код (на данный момент) более простым для чтения и изменения.
#define counter m[30] // name a memory location
mov 1000 counter
loop: // name a instruction pointer location
sub counter 1
(if not-zero) jmp-to loop
Одноуровневая подпрограмма : Предположим, вам нужно выполнить ряд шагов часто. Вы можете сохранить шаги в именованной позиции в памяти, а затем перейти к этой позиции, когда вам нужно выполнить их (вызвать). В конце последовательности вам нужно вернуть в точку , вызвав , чтобы продолжить выполнение. С помощью этого механизма вы создаете новые инструкции (подпрограммы), составляя основные инструкции.
Реализация: (новые концепции не требуются)
- Сохранить текущий указатель инструкций в предопределенной позиции памяти
- переход в подпрограмму
- в конце подпрограммы вы извлекаете указатель инструкций из предопределенной ячейки памяти, фактически возвращаясь к следующей инструкции исходного вызова
Проблема с реализацией one-level : Вы не можете вызвать другую подпрограмму из подпрограммы. Если вы это сделаете, вы перезапишете возвращающий адрес (глобальную переменную), поэтому вы не сможете вкладывать вызовы.
Чтобы иметь лучшую реализацию для подпрограмм: вам нужен STACK
Стек : Вы определяете пространство памяти для работы в качестве «стека», вы можете «выталкивать» значения в стек, а также «выталкивать» последнее «вытолкнутое» значение. Для реализации стека вам понадобится Указатель стека (аналогично указателю инструкций), который указывает на фактическую «верхушку» стека. Когда вы «нажимаете» значение, указатель стека уменьшается, и вы сохраняете значение. Когда вы щелкаете, вы получаете значение в фактическом указателе стека, а затем увеличивается указатель стека.
Подпрограммы Теперь, когда у нас есть стек , мы можем реализовать надлежащие подпрограммы , разрешающие вложенные вызовы . Реализация аналогична, но вместо того, чтобы хранить указатель инструкций в предопределенной позиции памяти, мы «помещаем» значение IP в стек . В конце подпрограммы мы просто «выталкиваем» значение из стека, фактически возвращаясь к инструкции после первоначального вызова . Эта реализация, имеющая «стек», позволяет вызывать подпрограмму из другой подпрограммы. С помощью этой реализации мы можем создать несколько уровней абстракции при определении новых инструкций в качестве подпрограмм, используя основные инструкции или другие подпрограммы в качестве строительных блоков.
Рекурсия : Что происходит, когда подпрограмма вызывает себя? Это называется "рекурсия".
Проблема: Перезапись locВсе промежуточные результаты подпрограмма может хранить в памяти. Поскольку вы вызываете / повторно используете одни и те же шаги, , если , промежуточный результат сохраняется в предопределенных ячейках памяти (глобальные переменные), они будут перезаписаны при вложенных вызовах.
Решение: Чтобы разрешить рекурсию, подпрограммы должны хранить локальные промежуточные результаты в стеке , следовательно, на каждом рекурсивном вызове ( прямые или косвенные) промежуточные результаты хранятся в разных местах памяти.
...
Наконец, обратите внимание, что у вас есть много возможностей использовать рекурсию. У вас есть рекурсивные структуры данных везде, сейчас вы смотрите на одну: части DOM, поддерживающие то, что вы читаете, - это RDS, выражение JSON - это RDS, иерархическая файловая система на вашем компьютере - это RDS, то есть: у вас есть корневой каталог, содержащий файлы и каталоги, каждый каталог, содержащий файлы и каталоги, каждый из этих каталогов, содержащий файлы и каталоги ...