蟻本の文脈上、このアルゴリズムは最大流アルゴリズムを真偽値を返すdfsで簡略化したように読めるのだが、その前提は理解を妨げるだけであるように思われるので忘れて欲しい。以下のように関数の役割を翻訳したほうがわかりやすい。
dfs := 与えられたノードvについて、隣接するノードuとマッチングを作ることができるならそれを行いtrueを返す。隣接するノードuが使われていたらそこから探索を行い、uがフリーになるようにつなぎ変えてtrueを返す。以上の二つが行えない場合falseを返して何もしない。
これをさらに言い換えれば、マッチングを増やせる時はtrueを返し、増やせない時にfalseを返すということになるので、全てのノードについてdfsを行えば最大マッチングになることも自然に納得されることと思う。（※マッチングを増やせる時というのが、つまるところ増加パスが見つかった時にあたるのだが直感的ではない。）
以下に、上の流れを添えたdfsを載せるので参考にしてほしい。
bool dfs(int v){ //ノードvにマッチングが無ければ呼び出される。
used[v] = true;
rep(i, 0, sz(G[v])){ //vに隣接するノードを見ていく。
int u = G[v][i];
int w = match[u];
if(w < 0 || (!used[w] && dfs(w))){
//w < 0 : uにマッチングが無ければ、当然v-uをつないで良い。
//!used[w] && dfs(w)
// : wをuではないところにつなぎ替えられたらtrueになる。
match[u] = v;
match[v] = u;
return true;
}
}
return false;
}