Tail-Recursive Functions क्या हैं
In this page:
tailrec fun functionName(n: Type, accumulator: Type = initial): Type {
return if (baseCase) accumulator
else functionName(n - 1, newAccumulator) // last action
}The Stack Overflow Problem
एक normal recursive function जो खुद को कई बार call करता है, जैसे किसी बड़े number का factorial compute करना, call stack खत्म कर सकता है क्योंकि हर call अगली के खत्म होने का इंतज़ार करता है।
उदाहरण: The Stack Overflow Problem
// Define the function `factorial` taking `n` and returning a Long
fun factorial(n: Long): Long {
// Return `if (n <= 1) 1 else n * factorial(n - 1)` from this function
return if (n <= 1) 1 else n * factorial(n - 1)
}
// Entry point: execution of the program starts here
fun main() {
// Print "10! = ${factorial(10)}" to the console, with a trailing newline
println("10! = ${factorial(10)}")
}Login to try C/C++/Java/PHP code in the editor
Marking a Function tailrec
fun से पहले tailrec जोड़ना compiler से एक सही shape वाले recursive call को एक loop में बदलने के लिए कहता है, ताकि यह चाहे कितनी भी बार recurse करे constant stack space में चले।
उदाहरण: Marking a Function tailrec
tailrec fun factorial(n: Long, accumulator: Long = 1): Long {
// Return `if (n <= 1) accumulator else factorial(n - 1, n * accumulator)` from this function
return if (n <= 1) accumulator else factorial(n - 1, n * accumulator)
}
// Entry point: execution of the program starts here
fun main() {
// Print "10! = ${factorial(10)}" to the console, with a trailing newline
println("10! = ${factorial(10)}")
}Login to try C/C++/Java/PHP code in the editor
The Call Must Be in Tail Position
optimization लागू होने के लिए, recursive call function का आखिरी काम होना चाहिए -- इसके result का उपयोग n * factorial(...) जैसी किसी आगे की computation में नहीं हो सकता, यही वजह है कि इसके बजाय एक accumulator parameter उपयोग होता है।
tailrec function को optimize नहीं कर सकता तो यह एक warning देता है -- हमेशा इसे जांचें।उदाहरण: The Call Must Be in Tail Position
tailrec fun sumUpTo(n: Int, accumulator: Int = 0): Int {
// Return `if (n == 0) accumulator else sumUpTo(n - 1, accumulator + n)` from this function
return if (n == 0) accumulator else sumUpTo(n - 1, accumulator + n)
}
// Entry point: execution of the program starts here
fun main() {
// Print "Sum 1..100: ${sumUpTo(100)}" to the console, with a trailing newline
println("Sum 1..100: ${sumUpTo(100)}")
}Login to try C/C++/Java/PHP code in the editor
Tail Recursion for Large Inputs
चूंकि एक tailrec function एक loop में compile होता है, यह सुरक्षित रूप से बड़े inputs process कर सकता है जो एक साधारण recursive implementation में stack overflow कर देते।
उदाहरण: Tail Recursion for Large Inputs
tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
// Entry point: execution of the program starts here
fun main() {
// Print "GCD of 48 and 18: ${gcd(48, 18)}" to the console, with a trailing newline
println("GCD of 48 and 18: ${gcd(48, 18)}")
}Login to try C/C++/Java/PHP code in the editor
- किसी function को
tailrecचिह्नित करना जब इसका recursive call असल में आखिरी operation न हो, जिसके लिए compiler चेतावनी देगा और optimize करने से मना कर देगा। - यह भूल जाना कि किसी
tailrecfunction का recursive call किसीtry/catchblock के अंदर नहीं होना चाहिए या इसके return होने के बाद अतिरिक्त computation में wrap नहीं होना चाहिए। - यह मान लेना कि कोई भी recursive function सिर्फ keyword जोड़कर
tailrecबनाया जा सकता है; call का shape खुद qualify होना चाहिए।
tailreccompiler को किसी recursive function को आंतरिक रूप से एक iterative loop में optimize करने के लिए कहता है, बड़े inputs के लिए stack overflow से बचते हुए।- recursive call को function में बिल्कुल आखिरी operation होना चाहिए -- इसके result के साथ बाद में कुछ नहीं किया जा सकता।
- compiler चेतावनी देता है अगर
tailrecचिह्नित कोई function असल में optimize नहीं हो सकता, इसलिए आपको उस चेतावनी पर नज़र रखनी चाहिए। - Tail recursion recursive-style code को readable रखते हुए loop-जैसी performance और stack safety देता है।
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: