ｃ) 再帰を使った数値計算

• 準備的練習として、 ｎの階乗　は n-1の階乗 に ｎ をかけたもの
  　　数学では n! と書く。　英語ではfactorial。
  　　！ は １とされている
  -　注）階乗はｎの増大に対して爆発的な勢いで結果の数が大きくなり、
  　　ｎが１５程度で31bit（Int型のbit数；右図）を越えてしまい（桁あふれ）、
  　　正しい計算結果を示さなくなる。
  
  対策としては、 　　Int でなく Long型を使うという方法がある。
  　　（さらに大きな数を扱うための対処については本ページ末尾で）。
• なお、２のべき乗（たとえば 2**32）の計算をしても、 桁あふれは発生する。
  　　* こういった大きな数がどの規模のものになるか、 　　 見当はつけられるようにしておくといいだろう。

プログラム例

• まず作ってみた

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

• 関数の本体を囲むブレース {} は、 この例のように本体の中に式が１つならば、省略できる。

    def fac(n:Int):Int=
        if(n==0) 1
        else n * fac(n-1)
  

  • ただし、エディタからREPLにコピペして読み込ませたときに、動作しないこともあるので、 今回の実習では省略しないほうが無難。

• この関数に、正の数を与えると正しく動作する。

    scala> fac(5)
    res1: Int = 120
  
    scala> fac(10)
    res2: Int = 3628800
  

• が、負の数を与えるとエラーが発生する。
  • これは、フェンスとなる値（再帰呼出がいつかこれに ぶつかってこれ以上進行しないよう設定した値） である 0 を 越えたところから（値が小さくなる方向に）動いていくから。

• この問題は、一か所の変更（比較の演算子）だけで、とりあえず回避することができる。

    def fac(n:Int):Int=
        if(n<=0) 1
        else n * fac(n-1)
  

  • 右図で 0より小さい値（負の数）全体を厚みのあるフェンスに設定した、と考えることができる。
  • 数学的には階乗は自然数（0より大きい整数）に対して定義されていて、負の数は定義域の外なので、 厳密に見て正しいのはエラーを発生させることだが、 ここでは深入りしないことにする。

• Intでなく Long型にすると、より大きな数が扱える。

    def fac(n:Long):Long=
        if(n<=0) 1
        else n * fac(n-1)
  

  • Intは31bit, Longは63bitで数値を表す （正負の符号を表すために1bit)。
  • なので Longでも、扱えるデータサイズには限度がある。
  • fac(20) までは扱えるがfac(21)以上は 　　オーバーフローするようだ。

• math.BigInt クラスを使えば、無制限の桁数に対応している。

    def fac(n:math.BigInt):math.BigInt=
        if(n<=0) 1
        else n * fac(n-1)
  

  • 例えばfac(50)などの結果がどのぐらいの桁数になるか 試してみて下さい。

    scala> fac(1000).toString.length
    res25: Int = 2568