Recursion: आफैँलाई call गर्ने function
आफैँलाई call गर्ने function ले factorial निकाल्नुहोस्। Base case सम्मको हरेक call मा call stack एक frame ले बढेको, अनि हरेक call ले उत्तर फर्काउँदा घटेको हेर्नुहोस्, र recursive function लाई किन base case चाहिन्छ, बुझ्नुहोस्।
मूल अवधारणा
Recursive function ले समस्याको सानो रूपमा आफैँलाई call गरेर समस्या हल गर्छ; base case ले सबैभन्दा सानो रूपको उत्तर सिधै दिन्छ, त्यसैले call रोकिन्छन् र उत्तरहरू call stack हुँदै फर्कन्छन्
पाठ: Function र recursion
कुनै सङ्ख्याको factorial, n! लेखिने, n देखि 1 सम्मका सबै पूर्ण सङ्ख्याको गुणनफल हो: 4! = 4 × 3 × 2 × 1 = 24। ध्यान दिनुहोस्, 4! भनेको 4 × 3! मात्र हो, र 3! भनेको 3 × 2!। Function ले यही विचार प्रयोग गरेर आफैँलाई call गर्न सक्छ: fact(n) ले n × fact(n − 1) फर्काउँछ। यसलाई recursion भनिन्छ। हरेक call ले सानो call को उत्तर पर्खन्छ, त्यसैले call हरू call stack मा थुप्रिन्छन्, नयाँ माथि। तिनीहरू कतै रोकिनुपर्छ: base case, IF n <= 1 THEN RETURN 1, ले फेरि call नगरी सबैभन्दा सानो समस्याको उत्तर तुरुन्तै दिन्छ। अनि उत्तरहरू थुप्रोबाट तल फर्कन्छन्: fact(1) ले 1, fact(2) ले 2 × 1, fact(3) ले 3 × 2, पहिलो call ले आफ्नो उत्तर नपाउन्जेल।
के सिक्नुहुनेछ
- Recursive function र base case के हुन्, व्याख्या गर्नुहोस्।
- Recursive call बढ्दा र फर्कँदा call stack trace गर्नुहोस्।
- Recursive function ले फर्काउने मान अनुमान गर्नुहोस्।
- Base case नभए के बिग्रन्छ, व्याख्या गर्नुहोस्।
सुरु गर्नुअघि
- Function ले parameter लिएर मान कसरी फर्काउँछ, थाहा हुनुपर्छ।
सामग्री
- Call stack कोर्न कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- fact(4) चलाएर उत्तर, call को सङ्ख्या र सबैभन्दा गहिरो stack पढ्नुहोस्।
- Step गर्दै हरेक frame देखिएको र फर्केको हेर्नुहोस्।
- number = 6, अनि number = 1 (तुरुन्तै base case) गरेर हेर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।