🕌

再帰関数で頭をバグらせない

2022/12/14に公開

Golang

AtCoder

tech

はじめに

再帰関数を実装するときに個人的に頭がバグりがちなので、atcoderの過去問題から再帰の極意を学び、まとめます。
後半では実際に頭がバグりにくい実装手順で問題を解いていきます！

再帰の極意

終了条件を必ず書く
終了条件がないと無限ループに陥るので当たり前ですが、大事です。
再帰関数に頭をついて行かせない
再帰関数内で次の再帰が呼ばれた時についつい深い方へ深い方へ気を取られてしまいがちですが^[1]、今いる再帰関数について考えましょう。
行きがけ/帰りがけの挙動に注意する

func f(x int) {
    // 行きがけの処理
    f(x-1)
    // 帰りがけの処理
}

「行きがけ」とは次の再帰に入る前に行う処理で、「帰りがけ」とは一つ深い再帰から戻ってきた時に行う処理です。
複雑な再帰関数は帰りがけの処理があるイメージがあります。

変数に再帰関数を代入する
深さ優先探索（DFS）をする時に、main関数内で定義したテーブルを更新していきたい時が結構あります。その時はいちいち更新テーブルを変数に渡す必要があるのですが、main関数内の変数に再帰関数を代入すると更新テーブルをいちいち渡さなくても更新テーブルのスコープ内に再帰関数が定義できるので更新できて楽です。

例題

上の極意に注意しながら簡単な再帰と複雑な再帰を実装していきます！

Atcoder Beginners Contest 266 E

この問題は、後何回サイコロを振れるかの再帰を考えます。サイコロを振れる回数がだんだん減っていき、最後はx = 1の時です。

// あとx回サイコロを振ることができる時の期待値
func f(x int) float64 {
    // 終了条件
    if x == 1 {
        return (1+2+3+4+5+6) / 6
    }
}

f(x)を求めるにはf(x-1)が必要です。
f(x-1)で、「あとx-1回振れる時」の再帰に頭をついて行かせないように気をつけます。つまり、もうすでに値が分かっているものとして扱いましょう。

// あとx回サイコロを振ることができる時の期待値
func f(x int) float64 {
    // 終了条件
    if x == 1 {
        return float64(1+2+3+4+5+6) / 6
    }
    // あとx回振れる時の期待値を求める
    nxtE := f(x-1) // あとx-1回振れる時の期待値はすでに得られているものと考える
    nowE := 0.0
    for i := 1; i < 7; i++ {
        if float64(i) >= nxtE {
            nowE += float64(i)
        } else {
            nowE += nxtE
        }
    }
    nowE /= 6
    return nowE
}

Atcoder Beginners Contest 256 E

この問題はFunctional Graphで、連結成分ごとにただ一つだけ存在するcycleを検出する問題に帰着できます。再帰でのDFSでcycleを検出してみましょう。
まずは全体像からです。すべてのノードが連結であるとは限らないので、すべてのノードからdfsを行います。

var dfs func(now int) //関数の変数を宣言
dfs = func(now int) {
    // do something
}

for i:=0;i<n;i++ {
    dfs(i)　// どのノードからもdfsをする
}

cycleを検出するには探索済みノードかどうかの情報が欲しいですね。これをstateに持たせてみます。
DFS関数のロジックが少し書けそうです。ノードを探索していって、今訪れたノードが既に探索済みだったらcycle検出とします。これが終了条件です。

state := make([]int, n)
// 0: 未探索
// 1: 探索済み
var cycle []int

var dfs func(now int)
dfs = func(now int) {
    // 終了条件
    if state[now] == 1 {
        return // このreturn文に来た時にcycleが見つかった!!
    }
    state[now] == 1
    nxt := X[now] // Xは初めて出てきましたが次のノードを記録しているスライスです
    dfs(nxt)
}

for i:=0;i<n;i++ {
    cycle = make([]int, 0)
    dfs(i)
}

cycleはこれで見つけられそうですが、記録ができていません。今のままでは終了条件に入った時にcycleが存在するということしかわかっていません。
cycle開始のノード情報がわかるとよさそうな気がします。これをdfs関数の返り値にしてみましょう。返り値とすることで一つ深い階層から情報を伝播できます。再帰dfsのいいところですね！
-1をノードがcycle上にいないときの返り値としておきます。

state := make([]int, n)
// 0: 未探索
// 1: 探索済み
var cycle []int

var dfs func(now int) int // 返り値はcycle開始ノード
dfs = func(now int) int {
    // 終了条件
    if state[now] == 1 {
        return now // cycleの開始地点
    }

    state[now] = 1

    nxt := X[now]
    ret := dfs(nxt)
    // retが-1じゃない時: nowがcycle上のノード
    if ret != -1 {
        cycle = append(cycle, now)
        if ret == now {
            // cycle開始地点に帰ってきた = これ以降はcycleでないので-1
            return -1
        }
    }
    return ret
}

for i:=0;i<n;i++ {
    cycle = make([]int, 0)
    dfs(i)
}

これでcycleが見つけられますが、実はまだ考慮点があります。既にcycleが見つかった連結成分について考えます。未探索ノードから再度dfsを開始したとき、cycleを検出していなくても終了条件に入ってしまいます。^[2]
終了条件の判定が十分でないということなので、この場合のstateを増やしてみましょう。具体的には訪問済み状態を処理中、処理完了の二つの状態に分けます。するとcycle検出は処理中の状態のノードに戻ってきた時に限定されます。

state := make([]int, n)
// 0: 未探索
// 1: 処理中
// 2: 処理完了
var cycle []int

var dfs func(now int) int
dfs = func(now int) int {
    // 終了条件
    if state[now] == 1 {
        return now // cycleの開始地点
    }
    if state[now] == 2 {
        // 処理完了ノードにやってきたら探索やめる
        return -1
    }

    state[now] = 1

    nxt := X[now]
    ret := dfs(nxt)

    state[now] = 2
    if ret != -1 {
        cycle = append(cycle, now)
        if ret == now {
            return -1
        }
    }
    return ret
}

for i:=0;i<n;i++ {
    cycle = make([]int, 0)
    dfs(i)
}

これで完成です!!
実際の解答コードはこちら

終わりに

ABC256 E問題を理解して解きたかったがために再帰関数から復習してみました。問題の解説メインになってしまいタイトル詐欺になったかもしれません。

脚注

自分だけですかね？ ↩︎
図を書くと分かりやすいです ↩︎

GitHubで編集を提案