Scalaビギナーズ関西 #2 の課題の解答例です。

takashikun.scala

/**
 * たかし君が階段をのぼります。
 * 課題：たかし君は階段を1段ずつ、または2段ずつ(1段飛ばし)でのぼるかをまぜてのぼることができます。
 * 10段のぼるには、何通りののぼり方がありますか。
 *
 * #scala_kansai_beginners
 */

val firstStep1 = 1 :: Nil // 最初の1歩は1段
val firstStep2 = 2 :: Nil // 最初は1歩は2段

def patternsToArriveAt(step:Int): List[List[Int]] = step match {
  case 1 => firstStep1 :: Nil // 1歩で1段しかありえない
  case 2 => (1 :: firstStep1) :: firstStep2 :: Nil // 2歩の場合と1歩の場合がある
  case _ => {
    patternsToArriveAt(step - 1).map(        // 目的の1段前にたどり着く全パターン
      aPattern => 1 :: aPattern              // ...に対してプラス1段
    ) ::: patternsToArriveAt(step - 2).map(  // 目的の2段前にたどり着く全パターン
      aPattern => 2 :: aPattern              // ...に対してプラス2段
    )                                        // を合体するとその段にたどり着く全パターン
    // (※ 2段前+1+1 を含めないのは、1段前の1段前+1 で考えたパターンと重複するから)
  }
}

val result = patternsToArriveAt(10)
result.foreach(println)
// result に対して、すべて合計10だとか、パターンがユニークだとかを検証もできるよ

println(result.length)