再帰的に考える
ベースケースと再帰ステップを学びます。
「再帰的に考える」はCoddyKit上の無料Scala for Backend Engineering & Functional Programmingレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはScala for Backend Engineering & Functional Programming学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。
再帰とは何か
再帰とは、関数が同じ問題のより小さなバージョンを解くために自分自身を呼び出すことです。
Scalaでは、可変変数を使わずにループを表現できるため、再帰は関数型プログラミングと自然に適合します。
すべての再帰関数には、停止する方法と問題を小さくする方法の2つが必要です。
まずベースケースを決める
ベースケースとは、追加の再帰なしで関数が直接答えられる最も単純な入力です。
ベースケースがなければ、関数は永遠に自分自身を呼び出し続け、スタックオーバーフローでクラッシュします。
必ず再帰ステップより先にベースケースを設計してください。
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}最初の再帰関数
ここでは、1からnまでの数を合計する完全なプログラムを示します。
ベースケースは0を返し、再帰ケースはnと、それより小さいすべての数の合計を足します。
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15呼び出しを追跡する
再帰を理解するには、呼び出しを手作業で展開してみます。
sum(3)は3 + sum(2)になり、これは3 + 2 + sum(1)、さらに3 + 2 + 1 + sum(0)になります。
sum(0)が0を返して初めて、呼び出しの連鎖が1つの値に戻り、結果は6になります。
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6リストの再帰
リストは本質的に再帰的です。リストは空のNilか、先頭要素と、それより小さい末尾部分のどちらかです。
この形は再帰関数にそのまま対応します。空のリストがベースケースで、先頭要素と末尾部分への再帰が再帰ステップです。
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}末尾のパターンマッチング
::パターンは、空でないリストを先頭要素と末尾部分に分割します。
各再帰呼び出しは必ずより短いリストに対して行われるため、Nilに向かって確実に進みます。
これはScalaでリストを再帰的に走査する標準的な方法です。
def sumList(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sumList(t)
}
@main def run(): Unit =
println(sumList(List(1, 2, 3, 4))) // 102つの再帰呼び出し
問題によっては、複数の再帰呼び出しに分岐します。
典型的な例がフィボナッチ数列で、各値が直前の2つの値に依存します。
この素朴な実装は単純ですが、同じ値を何度も再計算するため低速です。
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13スタックのコスト
再帰呼び出しのたびにコールスタックへフレームが追加され、内側の呼び出しが戻るまで待機します。
非常に深い再帰ではスタックを使い果たし、StackOverflowErrorが発生することがあります。
このリスクを予測するには、単なるデータ量ではなく深さを数えることが役立ちます。
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowErrorベースケースに向かって小さくする
再帰の重要な不変条件は、すべての呼び出しがベースケースに近づかなければならないことです。
引数が小さくならない、または停止条件に到達しない場合、再帰は終了しません。
実行する前にこれを確認してください。
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}再帰とループ
命令型コードでは可変カウンターを使うwhileループを使用し、関数型コードでは不変値を使う再帰を使用します。
どちらでも同じ計算を表現できますが、再帰のほうがデータの構造を直接的に表現できます。
Scalaでは、単純なループよりも再帰や高階関数を選ぶことがよくあります。
// Imperative
var total = 0
for (i <- 1 to 5) total += i
// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)再帰的な解法を設計する
信頼できる手順は、ベースケースを特定し、小さい入力に対する再帰呼び出しはすでに機能すると仮定してから、先頭要素とその結果を組み合わせることです。
この思い切った仮定が、再帰的に考える核心です。小さい入力への呼び出しを信頼し、1ステップだけを処理します。
def maxOf(xs: List[Int]): Int = xs match {
case h :: Nil => h
case h :: t => math.max(h, maxOf(t))
}
@main def run(): Unit =
println(maxOf(List(3, 9, 2, 7))) // 9理解度チェック
再帰構造についての理解を確認しましょう。
まとめ
再帰は、問題をそれ自体のより小さなインスタンスに置き換えて解決します。
すべての再帰関数には、停止するためのベースケースと、入力をそのベースケースに向かって小さくする再帰ステップが必要です。
Nilと先頭要素・末尾部分の形を持つリストは、再帰的な思考を学ぶ理想的な題材です。非常に大きな入力ではスタックの深さに注意してください。
よくある質問
「再帰的に考える」レッスンは無料ですか？
はい。「再帰的に考える」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Scala for Backend Engineering & Functional Programmingコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。
「再帰的に考える」で何を学びますか？
ベースケースと再帰ステップを学びます。 ブラウザで直接実行するハンズオンコードでScala for Backend Engineering & Functional Programmingを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Scala for Backend Engineering & Functional Programmingを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのScala for Backend Engineering & Functional Programmingは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「再帰的に考える」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このScala for Backend Engineering & Functional Programmingレッスンでコードを書いて実行できますか？
はい。すべてのScala for Backend Engineering & Functional Programmingレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。