部分和問題の再帰処理について

PHP
1// 部分和問題
2$arr =[1,2,4,7];
3$k=13;
4$n=4;
5
6function depth($arr, $k,$n,$sum=0, $i=0){
7    if($i == $n) {
8        return $sum == $k;
9    };
10    // 再帰A
11    if(depth($arr, $k,$n, $sum, $i+1)){ return true; }
12    // 再帰B
13    if(depth($arr, $k,$n, $sum+$arr[$i], $i+1)){ return true; }
14    
15    return false;
16    
17}
18
19var_dump(depth($arr, $k,$n,0,0));

上記のような関数があった時、再帰A,Bがどのような順序で呼ばれ、処理が終了するのか理解できません。
理解の助けとなる、サンプルやアイディアがあればご教授願います。

※再帰処理の特性として下記は多少なりとも理解しています。
・FILO(スタック)
・終了条件を定義する

行動規範の内容に同意します

回答2件

ベストアンサー

こんな感じの2分木を深さ優先探索します。青が false 部分、赤が true 部分、点線部が探索を行わなかった部分だと思ってください。

一番下まで来てれば $k と $sum の比較で true か false を返します。

中間層では、左側の探索（再帰A、$i番目の値を使わないケース）が true を返してくれば、そのまま上に true を返し、右側の探索は行わないです。
左側の探索が false を返してきた時は右側の探索（再帰B、$i番目の値を使うケース）を行い、これが true を返してくれば、上に true を返します。

どちらでもないケース、つまり左側も右側も false を返してきたケースでは、上に false を返します。

投稿2018/10/31 18:14

編集2018/10/31 18:57