fixedpoint.jp


「電話番号教えて」と言われたら (2022-06-21)

電話番号とは次のような整数列のことです:

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))

でも束の間で結果が出ます。


© 2006-2022 fixedpoint.jp