【初心者向け】後置インクリメントのタイミングを誤解していた話
はじめに
アルゴリズム問題をPHPで取り組んでいた時に、変数の後置インクリメントについて誤解していることが判明しました。
「あれ、予想した結果と違う」といった状況に出会した際、実はこのインクリメントの認識が違っていたということが原因になりえます。
そこで、この記事では、実際に筆者自身が後置インクリメントについて誤解していた点を整理しながら、後置インクリメントの挙動を解説していきます。
問題概要
PHPを使って、二分木 root を引数とした、最大の深さを返す、maximumDepth という関数を作成する問題に取り組んでいました。
※ ここでいう「最大の深さ」とは、根ノードから最も遠い葉ノードまでの最長経路に沿ったノードの数を指している、という問題の条件がありました。
なお、このアルゴリズム問題は、現在取り組んでいる、RecursionCSというプログラムの中で紹介されている問題です。
実装したコード
<?php
function maximumDepth(?BinaryTree $root): int
{
if($root === null) return 0;
if($root->left === null && $root->right === null) return 0;
return maximumDepthHelper($root, 0);
}
function maximumDepthHelper(?BinaryTree $root, int $count): int
{
$leftDepth = ($root->left !== null) ? maximumDepthHelper($root->left, $count++) : $count;
$rightDepth = ($root->right !== null) ? maximumDepthHelper($root->right, $count++) : $count;
return $leftDepth > $rightDepth ? $leftDepth : $rightDepth;
}
※リファクタリングの余地はありますが、最初に書いたコードを掲載しています。
実装の意図としては、再帰処理を含むことから、
根ノードを渡し結果を返すメイン関数と、根ノードから葉ノードに向かって再帰しながらノード数をカウントしていく補助関数に分けて、責務を分離しようとしました。
テストケース
1. `maximumDepth(toBinaryTree([0]))--> 0`
2. `maximumDepth(toBinaryTree([0,1,null]))--> 1`
3. `maximumDepth(toBinaryTree([0,-10,5,null,-3,null,9]))--> 2`
4. `maximumDepth(toBinaryTree([5,2,18,-4,3]))--> 2`
5. `maximumDepth(toBinaryTree([27,14,35,10,19,31,42]))--> 2`
6. `maximumDepth(toBinaryTree([30,15,60,7,22,45,75,null,null,17,27]))--> 3`
7. `maximumDepth(toBinaryTree([90,50,150,20,75,95,175,5,25,66,80,92,111,166,200]))--> 3`
8. `maximumDepth(toBinaryTree([50,17,76,9,23,54,null,null,14,19,null,null,72]))--> 3`
9. `maximumDepth(toBinaryTree([16,14,10,8,7,9,3,2,4,1]))--> 3`
10. `maximumDepth(toBinaryTree([30,15,60,7,22,45,75,1,null,17,27,null,null,null,null,-1]))--> 4`
直面した問題
取得した結果が、一部期待される出力結果より1少ない
原因
後置インクリメントのタイミングに対する誤解
当初の認識
新たに再帰関数 maximumDepthHelper($root, $count) の引数に $count を渡す際に $count + 1 された状態で渡される
正しい認識
再帰関数の引数に $count を渡す際に $count + 1 されない、つまり、$count の値はそのまま
後置インクリメントとは
変数の値を1増やすための演算子（インクリメント演算子）
言語は異なりますが、以下の例がこの誤解を解くために有用だと感じたため引用します。
let x = 3;
const y = x++;
console.log(`x:${x}, y:${y}`);
// Expected output: "x:4, y:3"
※ https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Increment より引用
ここからわかる処理の順番
- 評価
まず、x++はインクリメントされる前のxの値（このケースでは3）を評価されます。 - 代入
評価された値である3が、yに代入されます。 - インクリメント
その後、x自身の値が1増えて4になります。
つまり、変数に代入された時点ではxは3ですが、代入後にインクリメントされるため、上記のような出力結果になるということです。
これを先ほどの関数でいうと、 maximumDepthHelper($root, $count) の第二引数に $count を渡すときには、$count + 1 はされず、そのままの値を渡しているということになります。
まとめ
この記事では、後置インクリメントを使用した実装で実際に起きたエラーを紹介させていただきました。
エラーに直面したことによって、このような誤解を解くいいきっかけになったと思います。
使用する際には気をつけていきましょう！
最後までお読みいただき、ありがとうございました。
参考URL
Discussion