電話番号とは次のような整数列のことです:
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ...
(sequence A000085 in the OEIS)
これは\(n\)個の要素からなる順列のうちinvolutionであるもの全体の個数です。上の数列は\(n = 0\)から始まります。
漸化式で表せるため、Schemeでは容易に関数telephone-numberとして再帰的に定義できます:
(define (telephone-number n)
(if (<= n 1)
1
(+ (telephone-number (- n 1)) (* (- n 1) (telephone-number (- n 2))))))これで上記数列の先頭10個が計算できます:
(map telephone-number (iota 10))
しかし、これはcall stackをいたずらに消費するため非効率です。例えば、
(map telephone-number (iota 100))
はいつ計算が終わるか知れません。
telephone-numberを次のように末尾再帰で書けば、すぐに計算できるようになります。
(define (telephone-number n)
(let loop ((i 1)
(a 1)
(b 1))
(if (<= n i)
a
(loop (+ i 1) (+ a (* i b)) a))))これなら
(map telephone-number (iota 1000))
でも束の間で結果が出ます。