Recursion ले युक्लिडको GCD
आफैँलाई call गर्ने function ले दुई सङ्ख्याको सबैभन्दा ठूलो साझा भाजक (GCD, म.स.) निकाल्नुहोस्: gcd(a, b) ले gcd(b, a % b) लाई call गर्छ, र शेष 0 नभएसम्म सङ्ख्याहरू सानो हुँदै जान्छन्। Call stack हेर्नुहोस्, call गन्नुहोस्, र कुन जोडीको 1 बाहेक साझा भाजक छैन पत्ता लगाउनुहोस्।
मूल अवधारणा
युक्लिडको नियम gcd(a, b) = gcd(b, a % b) ले हरेक call मा सङ्ख्या सानो बनाउँछ, त्यसैले recursive function आफ्नो base case, b = 0, मा पुग्छ, जहाँ उत्तर a हो
पाठ: Function र recursion
दुई सङ्ख्याको सबैभन्दा ठूलो साझा भाजक (GCD), जसलाई म.स. (HCF) पनि भनिन्छ, दुवैलाई निःशेष भाग जाने सबैभन्दा ठूलो सङ्ख्या हो। दुई हजारभन्दा बढी वर्ष पहिले युक्लिडले छिटो तरिका भेट्टाए: a र b को GCD भनेको b र शेष a % b को GCD नै हो। त्यसैले gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0)। दोस्रो सङ्ख्या 0 हुँदा उत्तर पहिलो सङ्ख्या हो: यहाँ 6। यसले राम्रो recursive function बनाउँछ। gcd(a, b) मा base case हुन्छ, IF b == 0 THEN RETURN a, नत्र यसले gcd(b, a % b) फर्काउँछ। हरेक call सँग आफ्नै a र b हुन्छन्, र शेष सधैँ b भन्दा सानो हुने भएकाले सङ्ख्याहरू घट्दै जान्छन् र call रोकिनैपर्छ।
के सिक्नुहुनेछ
- युक्लिडको नियम लागू गर्न शेष % प्रयोग गर्नुहोस्।
- Base case र सानो recursive call भएको recursive function लेख्नुहोस्।
- Call stack मा call र तिनका argument trace गर्नुहोस्।
- दुई सङ्ख्याको GCD र call को सङ्ख्या अनुमान गर्नुहोस्।
सुरु गर्नुअघि
- Function ले parameter लिएर मान कसरी फर्काउँछ, र शेष भनेको के हो, थाहा हुनुपर्छ।
सामग्री
- हरेक call लेख्न कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- gcd(48, 18) चलाएर उत्तर र call को सङ्ख्या पढ्नुहोस्।
- Step गर्दै argument हरू घटेको हेर्नुहोस्।
- 1 बाहेक साझा भाजक नभएका 17 र 13 गरेर हेर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।