Первое, что я хотел бы поделиться, это то, что сложность в переводе этого на MIPS связана с наличием простого вызова функции, а не с тем, что рекурсия задействована - то, что fact рекурсивно, ИМХО красный сельдь . С этой целью я проиллюстрирую нерекурсивную функцию, которая имеет всю сложность заявленной вами рекурсивной функции:
int fact (int n)
{
if (n < 1) return 0;
else return n * other(n - 1); // I've changed the call to "fact" to function "other"
}
Мое изменение больше не является рекурсивным! Однако код MIPS для этой версии будет выглядеть идентично коду MIPS для вашего fact (за исключением, конечно, что jal fact, который меняет jal other). Это предназначено для иллюстрации того, что сложность в переводе связана с вызовом внутри функции и не имеет никакого отношения к тому, кто вызывается. (Хотя YMMV с методами оптимизации.)
Чтобы понять вызов функции, вам необходимо понять:
- счетчик программы: как программа взаимодействует со счетчиком программы, особенно Конечно, в контексте вызова функции ..
- передача параметров
- регистрация соглашений, обычно
В C у нас есть явные параметры. Эти явные параметры, конечно, также появляются на ассемблере / машинном языке, но есть также параметры, переданные в машинном коде, которые не видны в коде C. Примерами этого являются значение адреса возврата и указатель стека.
Здесь необходим анализ функции (независимо от рекурсии):
Параметр n будет в $a0 при входе в функцию. Значение n требуется после вызова функции (до other), потому что мы не можем умножить, пока этот вызов функции не вернет правый операнд *.
Следовательно, n ( левый операнд на *) должен пережить вызов функции на other, а на $a0 этого не произойдет - поскольку наш собственный код перенаправит $a0 для вызова other(n-1), так как n-1 must go в $a0 для этого.
Кроме того, (в C, неявный) параметр $ra содержит значение адреса возврата, необходимое для возврата нашему абоненту. Вызов other аналогичным образом переназначит регистр $ra, уничтожив его предыдущее значение.
Следовательно, для этой функции (вашей или моей) нужны два значения, чтобы пережить вызов функции, который находится внутри ее body (например, вызов other).
Решение простое: значения, которые нам нужны (которые живут в регистрах, которые перепрофилированы или уничтожены чем-то, что мы делаем, или потенциально вызываемый) нужно переместить или скопировать в другое место: куда-нибудь, что переживет вызов функции.
Для этого можно использовать память, и мы можем получить немного памяти для этих целей, используя стек.
На основе на этом мы должны сделать стековый фрейм, в котором есть место для двух вещей, которые нам нужны (и в противном случае были бы уничтожены) после вызова other. Запись $ra должна быть сохранена (и позже перезагружена), чтобы мы могли использовать ее для возврата; Кроме того, первоначальное значение n необходимо сохранить, чтобы мы могли использовать его для умножения. (Кадры стека обычно создаются в прологе функции и удаляются в эпилоге функции.)
Как это часто бывает в машинном коде (или даже в программировании в целом), существуют и другие способы обработки вещей, хотя суть та же. (Это хорошо, и оптимизирующий компилятор, как правило, ищет наилучший способ, учитывая конкретные обстоятельства.)
Наличие или отсутствие рекурсии не меняет фундаментальный анализ, который нам нужен для перевода этого в сборку. / машинный язык. Рекурсия значительно увеличивает вероятность переполнения стека, но в остальном не меняет этот анализ.
Приложение
Чтобы быть ясным, рекурсия накладывает требование использовать динамически расширяемый стек вызовов - хотя все современные компьютерные системы предоставляют такой стек для вызовов, поэтому это требование легко забыть или скрыть в современных системах.
Для программ без рекурсии стек вызовов не является обязательным - локальные переменные могут быть выделены глобальным переменным, закрытым для функций (включая адрес возврата), и это было сделано в некоторых старых системах, таких как PDP-8, которые не предлагали Speci c Аппаратная поддержка для стека вызовов.
Системы, которые используют память стека для передачи параметров и / или регистр не работает, может не требовать анализа, описанного в этом ответе, так как переменные уже хранятся в памяти, которая выдерживает вызовы вложенных функций.
Именно разделение регистров на современных машинах с большим количеством регистров создает требование для вышеуказанного анализа. Эти машины, богатые регистрами, передают параметры и возвращаемые значения (в основном) в регистрах ЦП, что эффективно, но требует иногда делать копии, когда регистры переназначаются из одной функции в другую.