再帰の基礎
再帰関数です。
「再帰の基礎」は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レッスンが含まれています。
再帰とは
再帰とは、関数が同じ問題をより小さくしたものを解くために、自分自身を呼び出すことです。関数型プログラミングと相性がよく、多くのループを自分自身を参照する定義で置き換えられます。
不可欠な2つの要素
正しい再帰関数には、必ず次の要素が必要です。
- 再帰を停止する基本ケース。
- 基本ケースに近づく再帰ケース。
到達可能な基本ケースがなければ、再帰は永遠に続きます。
階乗
典型的な例はn! = n * (n-1)!です。基本ケースは0! = 1です。
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}呼び出しを追跡する
再帰呼び出しはそれぞれ一時停止し、内側の結果を待ちます。factorial(3)は3 * (2 * (1))へ展開されます。乗算は、呼び出しが戻るときに実行されます。
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}リストの合計
リストに対する再帰では、合計は先頭要素と残りのリストの合計になります。空のリストの合計は0です。
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}リストの長さ
同じパターンで長さも計算できます。空のリストは0、それ以外は1と残りのリストの長さを足したものです。
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}コールスタック
保留中の再帰呼び出しはそれぞれスタックフレームを使用します。深い再帰では多くのフレームが積み重なります。非常に大きな入力ではスタックを使い果たし、StackOverflowErrorが発生することがあります。
フィボナッチ数列
問題によっては、再帰呼び出しが複数の分岐に分かれます。フィボナッチ数列は自分自身を2回呼び出すため簡潔ですが、計算量は指数関数的に増加します。
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}リストを反転する
再帰によって新しい構造を構築することもできます。反転処理では、残りのリストを反転してから先頭要素を末尾に追加します。
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}再帰と反復
ループではカウンターを変更しますが、再帰では問題を宣言的に表現します。どちらも有効な方法です。再帰は木構造のデータや分割統治に適していますが、単純な再帰は大きな線形入力でスタックオーバーフローを起こすおそれがあります。
最大公約数
ユークリッドのアルゴリズムは自然に再帰で表現でき、すばやく収束します。
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}理解度チェック
再帰の基本を確認しましょう。
まとめ
再帰の基本について学びました。
- すべての再帰関数には基本ケースと再帰ケースが必要です。
- 保留中の各呼び出しはスタックフレームを使用するため、深い再帰ではオーバーフローすることがあります。
- 再帰はリストや木構造のアルゴリズムを自然に表現できます。
次は、@tailrecアノテーションを使って再帰をスタックセーフにします。
よくある質問
「再帰の基礎」レッスンは無料ですか？
はい。「再帰の基礎」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと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フィードバックを取得できます。ローカル設定は不要です。