「なんで末尾呼び出しだと使うメモリの量が減るのか可視化してみた」by @naohaq さん

tailCall.hs

-- http://na.yuki.st/src/tailcall.txt より。

-- 末尾呼出でない定義
fact 0 = 1
fact n = n * fact (n - 1)

-- 末尾呼出な定義
fact' a 0 = a
fact' a n = fact' (a * n) (n - 1)

-- ******************************************--

-- 末尾呼出でない定義
fact 0 = 1
fact n = n * fact (n - 1)

-- 計算してみる
fact 20 = 20 * fact (20 - 1)
        = 20 * fact 19
        = 20 * (19 * fact (19 - 1))
        = 20 * (19 * fact 18)
        = 20 * (19 * (18 * fact (18 -1)))
        = 20 * (19 * (18 * fact 17))
        = 20 * (19 * (18 * (17 * fact (17 - 1))))
        = 20 * (19 * (18 * (17 * fact 16)))
        = 20 * (19 * (18 * (17 * (16 * fact 15))))
        = 20 * (19 * (18 * (17 * (16 * (15 * fact 14)))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * fact 13))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * fact 12)))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * fact 11))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * fact 10)))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * fact 9))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * fact 8)))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * fact 7))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * fact 6)))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * fact 5))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * fact 4)))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * fact 3))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * fact 2)))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * fact 1))))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * (1 * fact 0)))))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * (1 * 1)))))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * 1))))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * 2)))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * (4 * 6))))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * (5 * 24)))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * (6 * 120))))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * (7 * 720)))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * (8 * 5040))))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * (9 * 40320)))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * (10 * 362880))))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * (11 * 3628800)))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * (13 * (12 * 39916800))))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * (14 * 6227020800))))))
        = 20 * (19 * (18 * (17 * (16 * (15 * 87178291200)))))
        = 20 * (19 * (18 * (17 * (16 * 1307674368000))))
        = 20 * (19 * (18 * (17 * 20922789888000)))
        = 20 * (19 * (18 * 355687428096000))
        = 20 * (19 * 6402373705728000)
        = 20 * 121645100408832000
        = 2432902008176640000

-- ******************* --
-- 末尾呼出な定義
fact' a 0 = a
fact' a n = fact' (a * n) (n - 1)

fact' 1 20 = fact' (1 * 20) (20 - 1)
           = fact' 20 19
           = fact' (20 * 19) (19 - 1)
           = fact' 380 18
           = fact' (380 * 18) (18 - 1)
           = fact' 6840 17
           = fact' (6840 * 17) (17 - 1)
           = fact' 116280 16
           = fact' (116280 * 16) (16 - 1)
           = fact' 1860480 15
           = fact' (1860480 * 15) (15 - 1)
           = fact' 27907200 14
           = fact' (27907200 * 14) (14 - 1)
           = fact' 390700800 13
           = fact' (390700800 * 13) (13 - 1)
           = fact' 5079110400 12
           = fact' (5079110400 * 12) (12 - 1)
           = fact' 60949324800 11
           = fact' (60949324800 * 11) (11 - 1)
           = fact' 670442572800 10
           = fact' (670442572800 * 10) (10 - 1)
           = fact' 6704425728000 9
           = fact' (6704425728000 * 9) (9 - 1)
           = fact' 60339831552000 8
           = fact' (60339831552000 * 8) (8 - 1)
           = fact' 482718652416000 7
           = fact' (482718652416000 * 7) (7 - 1)
           = fact' 3379030566912000 6
           = fact' (3379030566912000 * 6) (6 - 1)
           = fact' 20274183401472000 5
           = fact' (20274183401472000 * 5) (5 - 1)
           = fact' 101370917007360000 4
           = fact' (101370917007360000 * 4) (4 - 1)
           = fact' 405483668029440000 3
           = fact' (405483668029440000 * 3) (3 - 1)
           = fact' 1216451004088320000 2
           = fact' (1216451004088320000 * 2) (2 - 1)
           = fact' 2432902008176640000 1
           = fact' (2432902008176640000 * 1) (1 - 1)
           = fact' 2432902008176640000 0
           = 2432902008176640000

ふつうの再帰呼び出しだと、一度山に登るまでは、値が求まらないところがポイント。末尾再帰のように途中結果のバトンをわたすのではなく、末端(山頂)に行き着くまで、問題を先送りしている。

末尾「再帰」といいつつ、実は、forループと同じなんだね・・ってとこまで理解できたら完璧

末尾呼び出しでない場合、自分自身を呼び出している間も値をキープしなければいけないところが大きな違い

途中の結果を書いたバトンを次の人(ステップ)に渡していく、というようなイメージ

末尾再帰→ある種の再帰呼び出しのことを指す
末尾再帰最適化→末尾再帰でコールスタックを積まないという最適化のことを指す