Recursion
Recursion tab hota hai jab ek function khud ko call karta hai, usually chhote input ke saath, jab tak ek "base case" na aa jaaye jaha function bina khud ko call kiye seedha answer de de. Har recursive function ke do zaroori hisse hain: base case (ruko yahan) aur recursive case (khud ko chhote problem ke saath call karo).
Internally, har recursive call apna naya stack frame banata hai (apni local variables ke saath) — jab base case hit hota hai, saare calls "unwind" hote hain (return karte hain) reverse order mein. Bina base case ke, recursion infinite chalega aur stack overflow karega.
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main() {
printf("%d\n", factorial(5)); // 5*4*3*2*1 = 120
return 0;
}
// Call stack: factorial(5) -> factorial(4) -> ... -> factorial(1)
// Phir unwind: 1 -> 2*1=2 -> 3*2=6 -> 4*6=24 -> 5*24=120- Har recursion mein base case (rukna) aur recursive case (khud ko call karna) zaroori
- Har call ka apna stack frame hota hai
- Bina base case = infinite recursion = stack overflow
Har recursive solution ko loop (iterative) se bhi likha ja sakta hai, aur usually iteration zyada efficient hoti hai (koi function-call overhead nahi, koi stack-overflow risk nahi). Recursion tab better lagta hai jab problem khud "recursively defined" ho — jaise tree traversal, ya divide-and-conquer algorithms (merge sort, quick sort).
// Recursive:
int factorialR(int n) {
if (n <= 1) return 1;
return n * factorialR(n - 1);
}
// Iterative (same result, koi extra stack frames nahi):
int factorialI(int n) {
int result = 1;
for (int i = 2; i <= n; i++) result *= i;
return result;
}Tail recursion ek special case hai jaha recursive call function ka SABSE AAKHRI operation hai (uske baad kuch aur calculate nahi hota). Kuch compilers ise automatically loop mein convert kar dete hain ("tail call optimization"), stack frames bachate hue — lekin C mein ye guarantee nahi hai (compiler-dependent).
// NOT tail recursive — multiplication call ke BAAD hoti hai:
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // call ke baad multiply karna hai
}
// Tail recursive — call hi last operation hai:
int factorialTail(int n, int acc) {
if (n <= 1) return acc;
return factorialTail(n - 1, acc * n); // koi kaam call ke baad nahi
}