tailrec関数
再帰を最適化します
「tailrec関数」はCoddyKit上の無料Kotlin Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはKotlin Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Kotlin Academyコースには全4レッスンが含まれています。
末尾再帰とは
再帰呼び出しが最後の操作になっている関数を末尾再帰関数と呼びます。この場合、Kotlin は再帰をループに最適化できるため、スタックオーバーフローを回避できます。
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}tailrec 修飾子
tailrec 修飾子を付けると、コンパイラーは再帰を反復処理に書き換え、スタック領域を一定量に抑えます。
tailrec fun sum(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return sum(n - 1, acc + n)
}
fun main() {
println(sum(100))
}アキュムレーターのパターン
再帰を末尾再帰の形にするには、アキュムレーターパラメーターに結果を渡し、呼び出しの後に計算が残らないようにします。
tailrec fun factorial(n: Int, acc: Long = 1): Long {
if (n <= 1) return acc
return factorial(n - 1, acc * n)
}
fun main() {
println(factorial(10))
}呼び出しを最後にする理由
再帰呼び出しの後に何らかの処理（結果の乗算など）があると、その呼び出しは末尾位置にならず、最適化できません。
tailrec fun length(s: String, acc: Int = 0): Int {
if (s.isEmpty()) return acc
return length(s.drop(1), acc + 1)
}
fun main() {
println(length("hello"))
}末尾再帰でない例
この階乗関数は、呼び出しから戻った後に乗算を行うため、末尾再帰ではありません。これに tailrec を付けると警告が表示されます。
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}スタックオーバーフローの回避
tailrec を使わない深い再帰は、クラッシュの原因になることがあります。tailrec を使えば、大きな入力でもスタック領域を一定量に抑えて実行できます。
tailrec fun count(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return count(n - 1, acc + 1)
}
fun main() {
println(count(100000))
}コンパイラーによる検証
関数に tailrec を付けても呼び出しが末尾位置にない場合、コンパイラーは警告を出し、最適化を行いません。警告を無視しないでください。
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}末尾再帰とループの比較
tailrec 関数は、同等のループとほぼ同じコードにコンパイルされますが、アルゴリズムを再帰的に表現できます。
tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
if (n == 0) return acc
return powerOfTwo(n - 1, acc * 2)
}
fun main() {
println(powerOfTwo(10))
}複数のパラメーター
末尾再帰関数では、複数の状態パラメーターを引き渡し、それらを再帰呼び出しですべて更新することがよくあります。
tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fib(n - 1, b, a + b)
}
fun main() {
println(fib(20))
}tailrec による反転
アキュムレーターを使うと、反転した文字列のような結果を構築できます。
tailrec fun reverse(s: String, acc: String = ""): String {
if (s.isEmpty()) return acc
return reverse(s.drop(1), s.first() + acc)
}
fun main() {
println(reverse("kotlin"))
}実用的な検索
反復的な検索は、末尾再帰に自然に置き換えられます。
tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
if (i >= list.size) return -1
if (list[i] == target) return i
return indexOf(list, target, i + 1)
}
fun main() {
println(indexOf(listOf(5, 6, 7), 7))
}理解度チェック
tailrec 関数についての理解度を確認しましょう。
まとめ
tailrec 関数について学びました。
tailrecは末尾位置の再帰をループに変換し、スタックオーバーフローを回避します。- 再帰呼び出しは最後の操作でなければなりません。
- アキュムレーターのパラメーターを使って末尾再帰の形にします。
- 関数を最適化できない場合、コンパイラーが警告します。
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}よくある質問
「tailrec関数」レッスンは無料ですか？
はい。「tailrec関数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Kotlin Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Kotlin Academyコースには全4レッスンが含まれています。
「tailrec関数」で何を学びますか？
再帰を最適化します ブラウザで直接実行するハンズオンコードでKotlin Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Kotlin Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのKotlin Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「tailrec関数」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このKotlin Academyレッスンでコードを書いて実行できますか？
はい。すべてのKotlin Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Infix関数
- DSL風APIの構築
- tailrec関数
- 使い分け