矩阵乘法递归求解

给定两个N×N的矩阵，求乘积

如下图所示，乘法执行过程如下：

1.矩阵1先拿出一行，矩阵2先拿出一列

2.行与列相乘得到value1

3.行与剩下矩阵2相乘得到value2（递归过程）

4.剩下矩阵1与列相乘得到value3（递归过程）

5.剩下矩阵1与剩下矩阵2相乘得到value4（递归过程）

6.将value1~value4合并成结果数组

写代码时注意约定，value1一定是数值，value2、value3、value4是数值、空数组或者非空的二维数组

由php实现，大体思路不难，但是要非常注意合并结果的细节：

<?php

class MatrixProduct
{
    protected $matrix1, $matrix2;
    protected $result;

    public function __construct($matrix1, $matrix2)
    {
        $this->matrix1 = $matrix1;
        $this->matrix2 = $matrix2;
        $this->result = $this->matrixProduction($this->matrix1, $this->matrix2);
    }

    public function show()
    {
        foreach ($this->result as $row) {
            foreach ($row as $data) {
                printf('%5d', $data);
            }
            echo PHP_EOL;
        }
    }

    protected function popRow(&$matrix)
    {
        return empty($matrix) ? [] : [array_shift($matrix)];
    }

    protected function popColumn(&$matrix)
    {
        $column = [];
        foreach ($matrix as $key => &$row) {
            $data = array_shift($row);
            if (empty($data) || empty($row)) {
                unset($matrix[$key]);
            }
            $column[] = [$data];
        }
        return $column;
    }

    protected function countProduction($row, $column)
    {
        for ($i = 0, $sum = 0; $i < count($row[0]); $i++) {
            $sum += $row[0][$i] * $column[$i][0];
        }
        return $sum;
    }

    protected function merger($value1, $value2, $value3, $value4)
    {
        if (empty($value2) && empty($value3)) {
            return $value1;
        } else {
            $array12 = array_merge([$value1], !is_array($value2) ? [$value2] : $value2[0] ?? []);
            if (!is_array($value3)) {
                $array34 = array_merge([$value3], !is_array($value4) ? [$value4] : $value4[0] ?? []);
                return [$array12, $array34];
            } else {
                for ($i = 0, $array34 = []; $i < count($value3); $i++) {
                    $array34[] = array_merge($value3[$i], $value4[$i] ?? []);
                }
                return array_merge([$array12], $array34);
            }
        }
    }

    protected function matrixProduction($matrix1, $matrix2)
    {
        $row = $this->popRow($matrix1);
        $column = $this->popColumn($matrix2);
        if (empty($row) || empty($column)) {
            return [];
        }

        $value1 = $this->countProduction($row, $column);
        $value2 = $this->matrixProduction($row, $matrix2);
        $value3 = $this->matrixProduction($matrix1, $column);
        $value4 = $this->matrixProduction($matrix1, $matrix2);

        return $this->merger($value1, $value2, $value3, $value4);
    }
}

$matrix1 = [
    [1, 2, 3, 4],
    [1, 2, 3, 4],
    [1, 2, 3, 4],
    [1, 2, 3, 4],
];

$matrix2 = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
];

$production = new MatrixProduct($matrix1, $matrix2);
$production->show();