पुनरावर्तन

पुनरावर्ती परिभाषाएँ

क्रमगुणित

किसी प्राकृत संख्या $n$ का क्रमगुणित 1 से $n$ तक की प्राकृत संख्याओं का गुणनफल है: $n! = 1 \cdot 2 \cdots n$, इस परिपाटी के साथ कि $0! = 1$। इस सूत्र के बिंदु एक लूप छिपाते हैं, और पाठ लूप ने उसे लिखना सिखाया। किंतु वही परिभाषा एक और रूप भी स्वीकार करती है, जिसमें किसी लूप का उल्लेख नहीं है: $n$ का क्रमगुणित $n$ गुना $n - 1$ का क्रमगुणित है, और 0 का क्रमगुणित 1 है।

यह एक पुनरावर्ती परिभाषा है: यह $n$ के क्रमगुणित को एक छोटी संख्या के क्रमगुणित के द्वारा परिभाषित करती है। यह चक्रीय नहीं है, क्योंकि दूसरे नियम का हर प्रयोग एक सीढ़ी नीचे उतरता है और सीढ़ियाँ पहले नियम पर समाप्त होती हैं: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$। दोनों नियमों के नाम हैं। पहला आधार स्थिति है, जो किसी और चीज़ का सहारा लिए बिना परिणाम देती है; दूसरा पुनरावर्ती स्थिति है, जो समस्या को उसी समस्या के एक छोटे उदाहरण में बदल देती है।

C++ किसी फ़ंक्शन को स्वयं को कॉल करने देता है, और इससे परिभाषा लगभग शब्दशः उतर आती है।

#include <print>​// n का क्रमगुणित।// पूर्व-शर्त: 0 <= n <= 12 (इस सीमा का कारण आगे दिया गया है)।// पश्च-शर्त: n! = 1 · 2 · ... · n लौटाता है, जहाँ 0! = 1।int factorial(int n){    if (n == 0) {        return 1;                   // आधार स्थिति    }    return n * factorial(n - 1);    // पुनरावर्ती स्थिति}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

अनुबंध सजावटी नहीं है: $n = -1$ होने पर पुनरावर्ती स्थिति $-2$ के साथ कॉल करेगी, फिर $-3$ के साथ, और कभी 0 तक नहीं पहुँचेगी; और $13!$ एक int में नहीं समाता। कई परिचयात्मक पुस्तकें इस क्रमगुणित को आधार स्थिति if (n == 0 || n == 1) के साथ लिखती हैं, जो अनावश्यक पर हानिरहित है, और ऋणात्मक संख्याओं या परिणाम के आकार के बारे में कुछ नहीं कहतीं: उनका कोड $n < 0$ होने पर समाप्त नहीं होता और $13!$ से आगे निरर्थक परिणाम देता है। दोनों दोषों की जाँच उनके अपने अनुभाग में की जाएगी।

आधार स्थिति और पुनरावर्ती स्थिति

हर पुनरावर्ती फ़ंक्शन में एक या अधिक आधार स्थितियाँ होती हैं, जो सीधे हल होती हैं, और एक या अधिक पुनरावर्ती स्थितियाँ, जो उसी फ़ंक्शन को किसी सटीक अर्थ में छोटे आर्ग्युमेंट के साथ कॉल करती हैं और जो वह लौटाता है उसे जोड़ती हैं।

घात $x^n$, जहाँ $n$ प्राकृत संख्या है, $x^0 = 1$ और $x^n = x \cdot x^{n - 1}$ द्वारा परिभाषित होती है: यहाँ आकार घातांक है। किसी प्राकृत संख्या $n$ के अंकों का योग (2026 का $2 + 0 + 2 + 6 = 10$ है) इस प्रकार परिभाषित होता है: यदि $n < 10$, तो योग $n$ है, क्योंकि उसमें एक ही अंक है; अन्यथा, यह $\lfloor n / 10 \rfloor$ के अंकों का योग है, जो अंतिम अंक के बिना $n$ है, और उसमें वह अंतिम अंक, $n \bmod 10$, जोड़ा जाता है। यहाँ आकार अंकों की संख्या है।

#include <print>​// x की घात n।// पूर्व-शर्त: n >= 0।// पश्च-शर्त: x^n लौटाता है, जहाँ x^0 = 1।double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// n के दशमलव अंकों का योग।// पूर्व-शर्त: n >= 0।// पश्च-शर्त: n के अंकों का योग लौटाता है।int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("2026 के अंकों का योग: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.3752026 के अंकों का योग: 10

अतः पुनरावर्ती फ़ंक्शन लिखने का अर्थ दो प्रश्नों का उत्तर देना है: कौन-सी स्थितियाँ बिना सहायता के हल होती हैं, और किसी स्थिति का हल एक छोटी स्थिति के हल से कैसे प्राप्त होता है। यदि दोनों उत्तर सही हैं, तो फ़ंक्शन सही है, और आगे का अनुभाग यह सिद्ध करता है।