Factorial (Recursion)

Recursion क्या है

Recursion तब है जब एक method समस्या के छोटे version को हल करने को खुद को call करती है। Factorial classic उदाहरण है, क्योंकि n! को (n-1)! के रूप में लिखा जा सकता है। हर recursion को base case चाहिए — एक सरल स्थिति जो उसे रोके।

Recursion के रूप में factorial

Factorial की स्वाभाविक रूप से recursive परिभाषा है:

5! = 5 × 4!
4! = 4 × 3!
...
0! = 1   (base case)

हर factorial छोटे factorial इस्तेमाल करके define होता है, नीचे 0! = 1 तक। वो structure सीधे recursive method पर mapped होता है।

Java program

public class Factorial {
    static int factorial(int n) {
        if (n == 0)              // base case
            return 1;
        return n * factorial(n - 1);   // recursive call
    }
    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}

Method n के 0 होने पर 1 return करती है (base case), वरना n गुणा n-1 का factorial return करती है। हर call n घटाती है जब तक 0 न पहुँचे।

Dry run

Base case मायने रखता है

// गलत: कोई base case नहीं -> infinite recursion
static int bad(int n) {
    return n * bad(n - 1);   // कभी नहीं रुकता -> StackOverflowError
}

Base case बिना, method हमेशा खुद को call करती है, call stack भरते हुए जब तक Java StackOverflowError न फेंके। हर recursion को रुकने की condition होनी चाहिए।

Loop बनाम recursion

• Recursion — सुंदर, गणित से मेल खाता है, पर call stack memory इस्तेमाल करता है।
• Loop — ज़्यादा कुशल, कोई गहरा stack नहीं, बड़े n को बेहतर।

दोनों वही जवाब देते हैं। समझ को recursion सीखिए; performance मायने रखे तब loop इस्तेमाल कीजिए।

आम गलतियाँ

• Base case गायब। Infinite recursion और StackOverflowError देता है।
• गलत base case value। 0! = 1, 0 नहीं।
• n न घटाना। हर call को base case की ओर बढ़ना चाहिए।
• बड़े n पर गहरा recursion। बहुत बड़ा n stack overflow कर सकता है — loop इस्तेमाल कीजिए।

सारांश

• Recursion एक method का छोटी समस्या पर खुद को call करना है।
• Factorial: n * factorial(n-1), base case 0! = 1।
• Base case recursion रोकता है — कभी मत छोड़िए।
• Calls return होते हुए results वापस गुणा होते हैं।
• बड़े n या बेहतर performance को इसके बजाय loop इस्तेमाल कीजिए।

आगे, recursion देखिए Floyd's triangle में, या loops से तुलना कीजिए Java loops में।