Recursion क्या है
func name(n int) int {
if n <= baseCase {
return value
}
return name(n - 1)
}A Basic Recursive Function
एक recursive function खुद को call करता है, आमतौर पर हर बार एक छोटे या सरल input के साथ, जब तक यह एक base case तक न पहुंचे जिसका बिना और recursion के सीधे जवाब दिया जा सके। Factorial classic पहला उदाहरण है।
उदाहरण: A Basic Recursive Function
// Every Go file belongs to a package; main builds an executable
package main
// Import the fmt package
import "fmt"
// Define the function factorial
func factorial(n int) int {
// Check whether n <= 1
if n <= 1 {
// Send 1 back to the caller
return 1
}
// Send n * factorial(n-1) back to the caller
return n * factorial(n-1)
}
// main is where the program starts running
func main() {
// Print the values followed by a newline
fmt.Println(factorial(5))
}Login to try C/C++/Java/PHP code in the editor
The Importance of a Base Case
recursion को रोकने वाले base case के बिना, एक recursive function हमेशा के लिए खुद को call करता है (जब तक program stack खत्म होने से crash न हो जाए)। base case वह है जो calls की एक अंतहीन chain को एक असल में terminate होने वाले function में बदल देता है।
उदाहरण: The Importance of a Base Case
// Every Go file belongs to a package; main builds an executable
package main
// Import the fmt package
import "fmt"
// Define the function countdown
func countdown(n int) {
// Check whether n <= 0
if n <= 0 {
// Print the values followed by a newline
fmt.Println("liftoff!")
return
}
// Print the values followed by a newline
fmt.Println(n)
countdown(n - 1)
}
// main is where the program starts running
func main() {
countdown(3)
}Login to try C/C++/Java/PHP code in the editor
Recursion on Recursive Data
Recursion उस data के लिए खासतौर पर स्वाभाविक है जो खुद recursively structured है, जैसे किसी slice का पहला element बाकी के sum में जोड़कर sum compute करना -- हर recursive call एक जैसी समस्या के shape का एक छोटा टुकड़ा handle करता है।
उदाहरण: Recursion on Recursive Data
// Every Go file belongs to a package; main builds an executable
package main
// Import the fmt package
import "fmt"
// Define the function sumSlice
func sumSlice(nums []int) int {
// Check whether len(nums) == 0
if len(nums) == 0 {
// Send 0 back to the caller
return 0
}
// Send nums[0] + sumSlice(nums[1:]) back to the caller
return nums[0] + sumSlice(nums[1:])
}
// main is where the program starts running
func main() {
// Print the values followed by a newline
fmt.Println(sumSlice([]int{1, 2, 3, 4, 5}))
}Login to try C/C++/Java/PHP code in the editor
- एक base case भूल जाना, जिससे stack overflow से program crash होने तक infinite recursion होता है।
- memoization के बिना recursive Fibonacci या समान लिखना, बड़े inputs के लिए exponential recomputation का कारण बनते हुए।
- यह मान लेना कि Go कुछ functional languages की तरह tail-recursive calls को अपने आप optimize करता है -- यह नहीं करता, इसलिए गहरी recursion अब भी stack space खर्च करती है।
- एक recursive function original समस्या के एक छोटे version के साथ खुद को call करता है।
- हर recursive function को recursion रोकने के लिए एक base case चाहिए।
- Go tail-call optimization नहीं करता, इसलिए बहुत गहरी recursion stack खत्म कर सकती है।
- Recursion उन समस्याओं के लिए स्वाभाविक रूप से उपयुक्त है जिनकी स्वाभाविक रूप से recursive structure हो, जैसे tree traversal।
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: