再帰処理はプログラマーの嗜み！エレガントにかけて当たり前！・・・と自信を持って言いたいところだが、自分は正直なところ苦手である。

日頃再帰処理を書く機会といえばコーディングクイズくらいで実際のところあまり書く機会がない..

再帰処理はケースによってはメモ化や末尾最適化までエレガントにやらないと計算量が大きくなったり、メモリを食うだけのコードになってしまうが、アルゴリズムによってはシンプルなコードになるというメリットがある。

が、認知負荷の高さは変わらない気がする。

何が認知負荷を高めているのか、苦労させているのかということを考えてみたのだが、自分の中で2つ気づいたことがあるのでそれについて書き残しておく。

return

何がいつreturnされるかわかりづらい、掴みづらい。

例えば次のようなケースは単純なコードなのでわかりやすいが、再帰ケースが複数になったりすると認知負荷が高くなる。

package main

import "fmt"

func fact(n int) int {
        // 基本ケース
	if n < 2 {
		return 1
	}
        // 再帰ケース
	return n * fact(n-1)
}

func main() {
	fmt.Println(fact(5)) // 120
}

returnで混乱する場合は愚直に処理を書き出してみるのが良いと思う。他に良い方法あるかな。

スタック

再帰関数の評価はコールスタックに積まれていく。スタックなのでLIFO。

評価が完了するとスタックからデータを取り出して処理していく。

ということが理解できていないとデバッガでコードを追っかけても途中で迷子になってしまう。

例えば次のような単純なコードだと考えやすい。

package main

import "fmt"

func proc(n int) {
	if n == 0 {
		return
	} else {
		fmt.Printf("%d", n)
		proc(n - 1)
		fmt.Printf("%d", n)
		return
	}
}

func main() {
	proc(5) // 5432112345
}

とても基本的なことかもしれないけど、コードが複雑になるほどわけのわからないことになるのでそういうときはこの基本に立ち返りたい。

所感

漸化式を導出して数学的に考えることができる、慣れていれば難しく感じる度合いが減りそうな気がするが、再帰はやっぱり苦手さが拭えないので鍛錬が必要。。。

forのループでまず書いてみて、その後再帰処理に書き換えてみるというアプローチもアリかなと思うが、問題によっては苦労するケースもあると思っている。

鍛錬して再帰が得意になったらまたこの記事を振り返ってみる。