Проблемы понимания рекурсии MiPS ASM?

Question

Пожалуйста, помогите мне понять эту формулу (если кому-то интересно, это алгоритм Needleman-Wunsch), я должен написать код, который использует рекурсию, но я не понимаю, как это сделать, у меня уже есть полная динамика версия написана, поэтому я знаю, как работает алгоритм, но я не знаю, как реализовать его с помощью рекурсии / стека. Я открыт для любых предложений.

Это формула:

Answer 1

Непонятно с чем у тебя проблемы. Эта формула уже рекурсивная, ничего особенного. Вы знаете, как создавать локальные переменные? Вам понадобится 3:

local i;
local j;
local max = F(i-1, j-1);
max += S(Ai, Bj);
register tmp = F(i, j-1) + d;
if (tmp > max) max = tmp;
tmp = F(i-1, j) + d;
if (tmp > max) max = tmp;
return max;

PS: предположительно у вас есть некоторые условия для начальных элементов, чтобы рекурсия не была бесконечной.