سبق Recursion

محب علوی نے 'پائتھون' کی ذیل میں اس موضوع کا آغاز کیا، ‏نومبر 2, 2012

ٹیگ:
  1. محب علوی

    محب علوی لائبریرین

    مراسلے:
    12,508
    جھنڈا:
    Pakistan
    موڈ:
    Bookworm
    کمپیوٹر سائنس کے طالب علموں کے لیے recursive پروگرامنگ کا موضوع عموما مشکل ثابت ہوتا ہے۔ یہ مشکل اس لیے ہے کہ یہ بظاہر دائری استدلال محسوس ہوتا ہے جو کہ سوچنے کا عمومی انداز نہیں۔ کمپیوٹر سائنس میں یہ ایک ایسا طریقہ ہے جس میں کسی مسئلہ کا حل منحصر ہوتا ہے اسے چھوٹے چھوٹے ٹکڑوں میں بانٹ کر حل کرنے میں اور یہ مرکزی نکتہ ہے کمپیوٹر سائنس میں۔
    عمومی طریقہ کار یہ ہوتا ہے کہ ایک مسئلہ کو ذیلی مسائل میں تقسیم کر دیا جاتا ہے ، پھر ان مسائل کو حل کیا جاتا ہے اور بعد ازاں نتائج کو جمع کر لیا جاتا ہے۔
    اسے تقسیم اور فتح (divide and conquer) طریقہ بھی کہا جاتا ہے، جب اسے لک اپ ٹیبل کے ساتھ ملایا جائے جس میں ذیلی مسائل کے نتائج کو محفوظ کیا جاتا ہے تو یہ ڈائنامک پروگرامنگ (dynamic programming) یا میمائزیشن(memoization) بھی کہلاتا ہے۔

    اس کی ایک سادہ تعریف یہ ہے کہ فنکشن جب خود اپنے کو بالواسطہ یا بلاواسطہ کال کرتا ہے۔

    recursive لوپ عموما لکھنے اور سمجھنے میں آسان ہوتی ہیں بمقابلہ iterative لوپ جیسا کہ while اور for ۔

    iterative لوپ کو بعض پروگرامنگ زبانوں میں اس لیے فوقیت دی جاتی ہے کہ یہ کم کمپیوٹر میموری استعمال کرتی ہیں اور نسبتا تیز ہوتی ہیں recursive لوپ۔
    کسی بھی iterative لوپ کو recursion کے طور پر لکھا جا سکتا ہے اور کسی بھی recursion کو iterative لوپ کے طور پر لکھا جا سکتا ہے۔
    اگر اطلاق کی وضاحت recursion سے ہوتی ہو تو اسے استعمال کرنا چاہیے ورنہ iterative لوپ کا استعمال کیا جانا چاہیے۔

    اگر recursion کبھی اپنے بنیادی کیس تک نہ پہنچ سکے اور وہ recursive بلاوے بلاتی چلی جائے تو پروگرام کبھی ختم نہیں ہوتا اور اسے infinite recursion کہتے ہیں۔

    حقیقتاً یہ پروگرام ہمیشہ نہیں چلتا رہتا بلکہ پائتھون ایک ایرر پیغام رپورٹ کر دیتا ہے جب maximum recursion depth تک رسائی ہو جاتی ہے۔
     
    • پسندیدہ پسندیدہ × 1
  2. محب علوی

    محب علوی لائبریرین

    مراسلے:
    12,508
    جھنڈا:
    Pakistan
    موڈ:
    Bookworm
    recursion پروگرامنگ زبانوں میں عموما اور پائتھون میں خصوصا پروگرام کی رفتار کو کم کر دیتی ہے۔

    recursion فنکشن کال کی وجہ سے سست ہوتی ہے ، C میں تو فنکشن کال فقط JUMP ہوتی ہے جبکہ پائتھون میں یہ نیم سپیس سکوپ سرچ (scope namespace search) , سٹیک سنبھالنا (stack handling) کی وجہ سے یہ بہت مہنگا آپریشن بن جاتی ہے اور اسے کرنے کی قیمت زیادہ ہونے کی وجہ سے الگورتھم کافی سست ہو جاتا ہے البتہ اسے بہتر کرنے کے کچھ طریقے ہیں جس میں ایک تکنیک memoization کی ہے جسے کئی زبانوں میں استعمال کیا جاتا ہے۔

    اس لیے پائتھون میں جہاں بھی اعادہ(iteration) یا تکرار(recursion) کی ضرورت ہو وہاں لوپ (loop) بہتر رہتی ہے recursive functions کے مقابلے میں عمومی طور پر۔

    سادہ recursion کی بجائے ایک طریقہ tail recursion کا ہے جس میں رفتار خاصی بڑھ جاتی ہے۔
     
    • پسندیدہ پسندیدہ × 1
    • معلوماتی معلوماتی × 1
  3. محب علوی

    محب علوی لائبریرین

    مراسلے:
    12,508
    جھنڈا:
    Pakistan
    موڈ:
    Bookworm
    recursion کی ایک کلاسیکل مثال کسی بھی مکمل عدد کا factorial فنکشن کے ذریعے معلوم کرنا ہے۔

    Pseudocode
    PHP:
    function factorial is:
    inputinteger n such that n >= 0
    output
    : [n × (n-1× (n-2× … × 1]
     
        
    1. if n is 0, return 1
        2. otherwise
    , return [ n × factorial(n-1) ]
     
    end factorial
    پائتھون کوڈ:
    PHP:
    def factorial(n):
              if (
    == 0):
                  return 
    1
              
    else:
                  return 
    factorial(1)
     
    • پسندیدہ پسندیدہ × 1
  4. محب علوی

    محب علوی لائبریرین

    مراسلے:
    12,508
    جھنڈا:
    Pakistan
    موڈ:
    Bookworm
    اگر n = 4 تو factorial کا فنکشن اس طرح سے چلے گا۔

    HTML:
    b4          = 4 * b3
                = 4 * 3 * b2
                = 4 * 3 * 2 * b1
                = 4 * 3 * 2 * 1 * b0
                = 4 * 3 * 2 * 1 * 1
                = 4 * 3 * 2 * 1
                = 4 * 3 * 2
                = 4 * 6
                = 24
     
    • پسندیدہ پسندیدہ × 1
  5. محب علوی

    محب علوی لائبریرین

    مراسلے:
    12,508
    جھنڈا:
    Pakistan
    موڈ:
    Bookworm
    کچھ مسائل کا حل recursion کے استعمال سے بہتر طور پر ممکن ہوتا ہے اور اس کام کے لیے بطور خاص استعمال کی جاتی ہے۔ چند مثالیں

    Tree traversal
    depth first search
    Divide and conquer algorithms



    Tail Recursion
    اس پر اگلی نشست میں بات ہوگی ۔
     
  6. عمار نقوی

    عمار نقوی محفلین

    مراسلے:
    553
    جھنڈا:
    India
    موڈ:
    Bookworm
    محب علوی بھائی مجھے recursion بالکل سمجھ نہیں آرہا۔
     
  7. محب علوی

    محب علوی لائبریرین

    مراسلے:
    12,508
    جھنڈا:
    Pakistan
    موڈ:
    Bookworm
    کوئی مسئلہ نہیں، یہ مشکل موضوع ہے اور ہر موضوع پہلی دفعہ یا چند دنوں میں سمجھ آ جائے ضروری نہیں۔
    recursion ہر کوڈ میں استعمال ہونے والی شے نہیں ، اس لیے یہ موضوع بعد میں توجہ اور زیادہ مثالوں سے سمجھنے کی کوشش کے لیے اٹھا رکھیں۔
    اگر ابھی سمجھنے کی ضد ہو تو اس لنک پر دیکھیں جہاں کافی تفصیل اور وضاحت سے تصاویر سے سمجھایا گیا ہے۔

    Python Recursion
     

اس صفحے کی تشہیر