[ruby] 再帰関数を用いた配列への要素の追加

Question

前提・実現したいこと

rubyを用いて競技プログラミングのような問題を解いています。
再帰関数の中で配列に要素を追加しています。
このときにarray.pushを用いると求めている結果と異なってしまいます。

該当のソースコード

問題の内容は関係ないのですが、簡略化したものを載せます。
・2次元の座標を上下左右のみ指定回数動く。
・同じ場所は通れない。
・12回移動するとき全部で何通りあるか。

# num：動く回数, hist：動いた履歴, :cur_pos：現在の場所
def move(num, hist = [], cur_pos = [0, 0])
  hist = [*hist, cur_pos] #これは動く
  # hist.push(cur_pos) #これは動かない
  return 0 if hist.count > num + 1
  return 1 if hist.count == num + 1

  around = [[0, 1], [0, -1], [1, 0], [-1, 0]]

  around.reduce(0) do |acc, ar|
    next_pos = [cur_pos[0] + ar[0], cur_pos[1] + ar[1]]
    hist.include?(next_pos) ? acc : acc + move(num, hist, next_pos)
  end
end

puts move(12)

試したこと

pushを用いずに配列に追加した場合は期待通りの結果となります。
なぜpushの場合は違うのでしょうか。
参照渡しであることが影響しているのかなとは思うのですがよくわかりません。
また、このコードの中で修正したほうが良い書き方（リファクタリング）があれば教えていただきたいです。

よろしくお願いいたします。

補足情報（FW/ツールのバージョンなど）

ruby v2.5.3

Answer 1

hist = [*hist, cur_pos]だと、新しいオブジェクトを作る、つまり、再帰呼び出しの階層ごとに違うオブジェクトになります。
hist.push(cur_pos)だと、同じオブジェクトに追加していく、つまり、再帰呼び出しの全ての階層で同じオブジェクトになります。

Comments

[aruto]

ご回答ありがとうございます。
"ローカル変数を更新する"という認識でコードを書いていたのですが
hist = [*hist, cur_pos]の場合は仮引数のhistを更新したのではなく、新しくhistというオブジェクトが作られる
hist.push(cur_pos)の場合は仮引数のhistがグローバル変数になる
という解釈であっていますでしょうか。
また後者についてなのですが、同名の変数があった場合ローカル変数が優先されるわけではないのでしょうか。

[otn]

hist = [*hist, cur_pos] は、新しいオブジェクトを作って、それでローカル変数のhistを更新します。
hist.push(cur_pos)は、ローカル変数が指しているオブジェクトをコピーせずに更新します。グローバル変数とか関係ないです。

[aruto]

ご返信ありがとうございます。
hist.push(cur_pos)では、次の再帰に実引数として異なるhistオブジェクトを渡しているつもりでいるが、実は同じオブジェクトを参照しているということですね。
だから、再帰全体でhistオブジェクトが共有されてしまい、期待通り動かないということですね。