\documentclass{scrartcl}
\RequirePackage{algorithm}
\RequirePackage{algorithmicx}
\RequirePackage[noEnd=false]{algpseudocodex}
\newcommand{\algorithmautorefname}{Algorithm} % Allow autoref.
% Define macros to typeset boolean in pseudocode environments
\algnewcommand{\True}{\textbf{\texttt{true}}}
\algnewcommand{\False}{\textbf{\texttt{false}}}
\algnewcommand{\NIL}{\textbf{\texttt{NIL}}}
\algnewcommand{\NULL}{\textbf{\texttt{null}}}
\input{definitions.tex}
\usepackage{mathtools}
\begin{document}

\begin{algorithm}
    \caption{Backtrack a single alignment in a recursive way}
    \begin{algorithmic}[1]
        \State $S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$),
        \Function{BacktrackRecurse}{$i$, $j$}
        \If {$i > 0$ and $j > 0$}
            \State $substitute = M[i-1][j-1]$
            \State $delete = M[i-1][j]$
            \State $insert = M[i][j-1]$
            \State $min = \min \{ substitute, delete, insert \}$
            \If {$substitute = min$}
                \State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j-1$}
                \State $z = \begin{pmatrix} S_{1}[i-1] \\ S_{2}[j-1] \end{pmatrix} \circ z$
            \ElsIf {$delete = min$}
                \State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$}
                \State $z = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix} \circ z$
                \Else
                \State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$}
                \State $z = \begin{pmatrix} \varepsilon \\ S_{2}[j-1] \end{pmatrix} \circ z$
            \EndIf
        \ElsIf {$i > 0$}
            \State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$}
            \State $z = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix} \circ z$
        \ElsIf {$j > 0$}
            \State $z = $ \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$}
            \State $z = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix} \circ z$
            \Else
            \State \Return []
        \EndIf
        \State \Return $z$
        \EndFunction
        \Function{Backtrack}{$S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$)}
        \State \Return \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $m$, $n$}
        \EndFunction
    \end{algorithmic}
\end{algorithm}

\begin{algorithm}
    \caption{Backtrack all the optimum alignments in a recursive way}
    \begin{algorithmic}[1]
        \Procedure{Recurse}{$S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$), $i$, $j$}
        \If {$i > 0$ and $j > 0$}
            \State $substitute = M[i-1][j-1]$
            \State $delete = M[i-1][j]$
            \State $insert = M[i][j-1]$
            \State $min = \min \{ substitute, delete, insert \}$
            \If {$substitute = min$}
                \State $value = \begin{pmatrix} S_{1}[i-1] \\ S_{2}[j-1] \end{pmatrix}$
                \State $z' = value \circ z$
                \State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j-1$, $z'$}
            \EndIf
            \If {$delete = min$}
                \State $value = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix}$
                \State $z' = value \circ z$
                \State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$, $z'$}
            \EndIf
            \If {$insert = min$}
                \State $value = \begin{pmatrix} \varepsilon \\ S_{2}[j-1] \end{pmatrix}$
                \State $z' = value \circ z$
                \State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$, $z'$}
            \EndIf
        \ElsIf {$i > 0$}
            \State $value = \begin{pmatrix} S_{1}[i-1] \\ \varepsilon \end{pmatrix}$
            \State $z' = value \circ z$
            \State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i-1$, $j$, $z'$}
        \ElsIf {$j > 0$}
            \State $value = \begin{pmatrix} \varepsilon \\ S_{2}[j-1] \end{pmatrix}$
            \State $z' = value \circ z$
            \State \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $i$, $j-1$, $z'$}
        \EndIf
        \State \Call{print}{$z$}
        \EndProcedure
        \Procedure{Backtrack}{$S_{1}$: Array($m$), $S_{2}$: Array($n$), $M$: Array($m+1$, $n+1$)}
        \State \Return \Call{BacktrackRecurse}{$S_{1}$, $S_{2}$, $M$, $m$, $n$, []}
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\end{document}

\end{document}
\iffalse
    \Function{AppendToAll}{$value$, $set$}
    \Returns {A new set with all elements from $set$ with value appended first to them }
    \State $res = \{\}$
    \For {$element \in set$}
        \State $element = value \circ element$
        \State $res = res \cup element$
    \EndFor
    \State \Return $res$
    \EndFunction
\fi