末尾再帰が半分ぐらいわかったメモ

関数型プログラミングって頭が柔らかくないと辛みがすごい....完全に今の自分は素人に戻っている。楽しいけど。

Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド

これを読んでいたら「末尾再帰」って言葉が出てきた。知らないのでググってみたら、ものすごい丁寧に解説してくれている方がいた。あなたが神か。

rn4ru.com

末尾再帰ではない再帰

再帰といえば階乗の計算ですね。

    def factorial(n:Int) :Int = {
        if(n == 1) n
        else n * factorial(n-1)
    }

これに5を入れて実行してみると、5→4→3→2→1とデクリメントされていく。1までいけば再帰呼び出しは終了され、factorial(n-1)の値が数珠つなぎに決定される。再帰呼び出しが停止されるまではずっと「呼出履歴」を保持することになる。コールスタックと呼ぶらしい。

冗長だが、上から並べるとこの再帰はこういう流れを取る。

処理の流れ
n = 5
n = 4
n = 3
n = 2
n = 1
1 * 1 = 1
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
5 * 24 = 120

factorial(2-1)まで掘り下げて求めたnを元に、その過程で呼び出したfactorialの計算が始まって120が戻ってくる。こうやって階乗を求めようとするって、ある意味すごい...

末尾再帰のコード

n が求まらない限り呼出履歴を持ち続けないといけないのは非効率なので、それを辞めようというのが末尾再帰の考え方のようだ。下記のような流れで階乗を求めましょう、と。

処理の流れ
5 * 1 = 5
4 * 5 = 20
3 * 20 = 60
2 * 60 = 120
1 * 120 = 120

上記のような処理の流れに切り替えれば、factorial(5,1) => factorial(4,5) => factorial(3,20)...と関数をn回呼び出せば済むでしょう、というスタイル。関数内で完結すればn回関数を呼ぶだけ。ループで実行して結果保持するだけでしょ、みたいな。ここが慣れが必要なポイントなんだろうか。

で、末尾再帰のコードはこういうコードになる。

    def factorialTail(n:Int,acc:Int): Int = {
        //println("n=" + n + " acc=" + acc)
        if(n == 1) acc
        else factorialTail(n-1,n*acc)
    }

printlnのコメントを外すと、こういう流れで処理が進んでいることがわかる。

n=5 acc=1
n=4 acc=5
n=3 acc=20
n=2 acc=60
n=1 acc=120

まとめ

末尾再帰になる条件は「再帰呼び出しを行う行がreturnと関数呼び出しだけで構成されていること」である、ということを学びました。

あわせて読みたい

rn4ru.com