Fibonacci: recursion आफैँलाई दोहोर्याउँदा
आफैँलाई दुई पटक call गर्ने function ले Fibonacci सङ्ख्या निकाल्नुहोस्। n बढ्दै जाँदा call गन्नुहोस्, call stack मा उही साना call बारम्बार भएको हेर्नुहोस्, र उत्तर सम्झिराख्नु किन धेरै छिटो हुन्छ, बुझ्नुहोस्।
मूल अवधारणा
fib(n) = fib(n − 1) + fib(n − 2), fib(0) = 0 र fib(1) = 1 सहित; हरेक call ले थप दुईवटा call गर्ने भएकाले call को सङ्ख्या निकै छिटो बढ्छ, र उही उत्तर धेरै पटक निकालिन्छ
पाठ: Function र recursion
Fibonacci सङ्ख्याहरू 0, 1, 1, 2, 3, 5, 8, 13 बाट सुरु हुन्छन्: हरेक सङ्ख्या आफूभन्दा अघिका दुईको योग हो। यो नियम सिधै recursive function बन्छ: fib(n) ले fib(n − 1) + fib(n − 2) फर्काउँछ, base case fib(0) = 0 र fib(1) = 1 सहित। यो छोटो र सही छ, तर यसको लुकेको मूल्य छ। Base case नभएको हरेक call ले थप दुईवटा call गर्छ, र तिनले फेरि दुई-दुईवटा। fib(5) ले fib(4) र fib(3) माग्छ, तर fib(4) ले पनि fib(3) माग्छ, त्यसैले fib(3) दुई पटक निकालिन्छ, fib(2) तीन पटक, यसै गरी। Call को सङ्ख्या उत्तरजत्तिकै छिटो बढ्छ। हरेक उत्तर थाहा भएपछि सम्झिराख्दा, भर्याङको Lab ले जस्तै, यो दोहोरिने काम सबै बच्छ।
के सिक्नुहुनेछ
- Fibonacci नियमलाई दुईवटा base case भएको recursive function का रूपमा लेख्नुहोस्।
- हरेक fib(n) ले call stack मा गर्ने दुईवटा call trace गर्नुहोस्।
- n बढ्दा call को सङ्ख्या कति छिटो बढ्छ, गन्नुहोस्।
- उत्तर सम्झिराख्दा किन छिटो हुन्छ, व्याख्या गर्नुहोस्।
सुरु गर्नुअघि
- Recursive function र यसको base case कसरी काम गर्छन्, थाहा हुनुपर्छ (factorial को Lab)।
सामग्री
- Call हरूको रूख कोर्न कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- fib(4) Step गर्दै call stack हेर्नुहोस्।
- n = 1, अनि n = 6 का लागि चलाएर call दाँज्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।