【Scala】再帰的定義

再帰的定義ってなに

関数の定義の中にその関数自身が現れる定義のこと。
例えば階乗 n! を求める関数 fact を作るとき

scala> def fact(n: Int):BigInt = if (n==0) 1 else n * fact(n-1)
fact: (n: Int)BigInt

scala> fact(5)  
res: BigInt = 120

factという関数の定義中にfactという関数を使用している。これが再帰的定義
あと、再帰的定義をするときは返り値を設定すること。

scala> def fact(n: Int) = if (n==0) 1 else n * fact(n-1)
<console>:8: error: recursive method fact needs result type
       def fact(n: Int) = if (n==0) 1 else n * fact(n-1)
//error

再帰的定義を使って色々な関数を作るよ

フィボナッチ数を計算する関数 fib を作る

scala> def fib(n:BigInt):Int = if(n<2) 1 else fib(n-1) + fib(n-2)
fib: (n: BigInt)Int

scala> fib(6)
res: Int = 13

リストでも再帰的定義。
リストの総和を求める関数 sum を作る

scala> list
res: List[Int] = List(1, 2, 3, 4)

scala> def sum(xs:List[Int]):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail)
sum: (xs: List[Int])Int

scala> sum(list)
res: Int = 10

xs.head は最終的に空リストを参照してしまうため、、空リストだったときのパターンを作らないとerror吐かれる。

scala> def sum(xs:List[Int]):Int = xs.head + sum(xs.tail)
sum: (xs: List[Int])Int

scala> sum(list)
java.util.NoSuchElementException: head of empty list

リストの要素をインクリメントさせる関数 mapInc

scala> def mapInc(xs:List[Int]):List[Int]  = if(xs.isEmpty) Nil else xs.head +  1 :: mapInc(xs.tail)
mapInc: (xs: List[Int])List[Int]

scala> mapInc(list)
res: List[Int] = List(2, 3, 4, 5)

リストで再帰的定義を使うタイミングなんてあまりない気がする