Recursion क्या है
In this page:
fn name(n: u64) -> u64 {
if n == base_case {
return value;
}
name(n - 1)
}A Simple Recursive Function
एक recursive function वह है जो खुद को call करता है, आमतौर पर एक छोटे input के साथ, एक base case की ओर काम करते हुए जो आगे recursive calls रोकता है।
उदाहरण: A Simple Recursive Function
// Define the function `factorial` taking `n` and returning an unsigned 64-bit integer
fn factorial(n: u64) -> u64 {
// Check whether `n == 0`
if n == 0 {
1
// Otherwise, run this branch
} else {
n * factorial(n - 1)
}
}
// Entry point: execution of the program starts here
fn main() {
// Print "5! = {}" to the console, substituting in `factorial(5)` (with a trailing newline)
println!("5! = {}", factorial(5));
}Login to try C/C++/Java/PHP code in the editor
The Base Case
हर सही recursive function को एक base case चाहिए: एक condition जहां यह आगे recurse करने के बजाय सीधे एक value return करता है। इसके बिना, function खुद को अंतहीन रूप से call करता रहेगा।
उदाहरण: The Base Case
// Define the function `countdown` taking `n`
fn countdown(n: i32) {
// Check whether `n == 0`
if n == 0 {
// Print "Liftoff!" to the console (with a trailing newline)
println!("Liftoff!");
return;
}
// Print "{}" to the console, substituting in `n` (with a trailing newline)
println!("{}", n);
countdown(n - 1);
}
// Entry point: execution of the program starts here
fn main() {
countdown(3);
}Login to try C/C++/Java/PHP code in the editor
Recursion on a Naturally Recursive Structure
कुछ problems, जैसे Fibonacci numbers compute करना, एक naturally recursive mathematical definition से मेल खाती हैं, एक recursive solution को विशेष रूप से clear बनाते हुए भले ही हर call दो और spawn करता हो।
उदाहरण: Recursion on a Naturally Recursive Structure
// Define the function `fibonacci` taking `n` and returning an unsigned 64-bit integer
fn fibonacci(n: u32) -> u64 {
// Check whether `n < 2`
if n < 2 {
n as u64
// Otherwise, run this branch
} else {
fibonacci(n - 1) + fibonacci(n - 2)
}
}
// Entry point: execution of the program starts here
fn main() {
// Print "fibonacci(10) = {}" to the console, substituting in `fibonacci(10)` (with a trailing newline)
println!("fibonacci(10) = {}", fibonacci(10));
}Login to try C/C++/Java/PHP code in the editor
Recursion vs Iteration
कई recursive functions को loops के रूप में फिर से लिखा जा सकता है, जो deep inputs पर stack overflow का जोखिम टालते हैं। Recursion चुनना अक्सर raw performance से ज़्यादा code clarity के बारे में है।
उदाहरण: Recursion vs Iteration
// Define the function `factorial_iterative` taking `n` and returning an unsigned 64-bit integer
fn factorial_iterative(n: u64) -> u64 {
// Declare a mutable variable `result`, initialized to `1`
let mut result = 1;
// Loop over `1..=n`, binding each item to `i`
for i in 1..=n {
result *= i;
}
result
}
// Entry point: execution of the program starts here
fn main() {
// Print "5! (iterative) = {}" to the console, substituting in `factorial_iterative(5)` (with a trailing newline)
println!("5! (iterative) = {}", factorial_iterative(5));
}Login to try C/C++/Java/PHP code in the editor
- एक base case लिखना भूल जाना, function को हमेशा के लिए खुद को call करने का कारण बनाते हुए जब तक program एक stack overflow से crash न हो जाए।
- ऐसी problems के लिए recursive solutions लिखना जो एक simple loop से iteratively बेहतर और ज़्यादा efficiently solve होती हैं।
- यह मान लेना कि Rust अपने आप tail-recursive calls को loops में optimize करता है -- यह tail-call optimization की गारंटी नहीं देता।
- एक recursive function खुद को एक छोटे या simpler input के साथ call करता है जब तक यह एक base case तक न पहुंच जाए।
- हर recursive function को कम से कम एक base case चाहिए जो recursion रोके।
- Deep recursion call stack खत्म कर सकता है; Rust कुछ functional languages की तरह tail-call optimization की गारंटी नहीं देता।
- Recursion naturally recursive structure वाली problems के लिए एक natural fit है, जैसे factorials या tree traversal।
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: