Question about a recursive definition of an algorithm

40 Views Asked by At

Consider the algorithm below.

enter image description here enter image description here

Applying the given algorithm above to $A_{11} = \begin{pmatrix}1 & 2 \\ 3 & 8\end{pmatrix},\ B_{11} = \begin{pmatrix}7 & 1 \\ 5 & 9\end{pmatrix}$ we get $A_{\color{red}{11}} = 1, \ A_{\color{red}{12}} = 2, \ A_{\color{red}{21}} = 3, \ A_{\color{red}{22}} = 8, \ B_{\color{blue}{11}} = 7, \ B_{\color{blue}{12}} = 1, \ B_{\color{blue}{21}} = 5, \ B_{\color{blue}{22}} = 9$ which are $1 \times 1$ so we must apply the base case to them which is $c_{11} = a_{11} \cdot b_{11} + c_{11}$. But how do we apply the base case to these $1 \times 1$ matrices? Ignoring the base case and simply applying the matrix multiplication procedure to these integers produces the correct answer, but shouldn't we fall back to the base case when $n = 1$? Does the base case only apply to the originally given matrices and not those gotten from applying the recursive steps?