「プログラマ脳を鍛える数学パズル」のQ8をPHPで解こうとしてエラーが出て困っています

Question

只今、独学でプログラミング勉強中です。
「プログラマ脳を鍛える数学パズル」という本に挑んでいますが8問目で悩んでいます。
本にはPHPでの回答は載っていないのでご教授いただきたいです。

問題は、
同じ場所を通らない掃除ロボットを考えます。このロボットは前後左右にのみ移動することができます。例えば、3回移動する場合、最初に後ろに移動する経路は以下の9パターンあります(画像参照)。最初の移動方向は前後左右があるので、考えられる移動経路は全部で9×4=36通りあります。
※最初の位置を「0」で、その後の移動位置を数字で表現しています。

このロボットが12回移動するとき、考えられる移動経路のパターンが何通りあるかを求めてください。
（引用：プログラマ脳を鍛える数学パズル）

答えは324932通りです。

これをPHPで以下のように考えてみましたが、PHP Fatal error: Allowed memory size ofエラーが出ます。
試しに第一引数を「3」にしても同じエラーが出るのでメモリを増やせばよい問題ではなく、私の記述がよくないのだと考えていますが、どこが悪いのか分かりません。
どなたか解答をいただければ幸いです。

function move($steps, $log) {
	if (count($log) == $steps + 1) {
		return 1;
	}

	$cnt = 1;
	$pattern = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // 進める位置

	foreach ($pattern as $pos) {
		$next = [end($log)[0] + $pos[0], end($log)[1] + $pos[1]];

		// 探索済みでなければ移動
		if (!in_array($next, $log)) {
			array_push($log, $next);
			$cnt += move($steps, $log);
		}
	}
	return $cnt;
}

echo move(12, [[0,0]]);

Comments

[jssa]

無断転載・複製を禁ず など記載されてませんでしたか？

[PenelopeG]

引用させていただいています。

Answer 1

$logにデータが追加される一方なので、すぐに$stepのサイズを超えて止まらなくなります。
追加した分取り除いてください

            array_push($log, $next);
            $cnt += move($steps, $log);
+           array_pop($log);

---

追記:

$cnt = 1;

ここが違います

Comments

[PenelopeG]

ありがとうございます。
確かに追加される一方になっていました。
教えていただいた方法でメモリー不足のエラーはなくなりましたが、
返ってきたのは「514897」で正解とは異なっていました。
試しに第一引数を「3」にしてみると「53」と返ってきました。
どこで間違っているのでしょうか。ご教授いただけると助かります。

[PenelopeG]

$cnt = 0;
でした。ご指摘ありがとうございました。