سبق Recursion

[محب علوی]

کمپیوٹر سائنس کے طالب علموں کے لیے 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 تک رسائی ہو جاتی ہے۔

 

[محب علوی]

​

recursion پروگرامنگ زبانوں میں عموما اور پائتھون میں خصوصا پروگرام کی رفتار کو کم کر دیتی ہے۔

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

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

سادہ recursion کی بجائے ایک طریقہ tail recursion کا ہے جس میں رفتار خاصی بڑھ جاتی ہے۔

​

​

 

[محب علوی]

recursion کی ایک کلاسیکل مثال کسی بھی مکمل عدد کا factorial فنکشن کے ذریعے معلوم کرنا ہے۔

Pseudocode

function factorial is:
input: integer 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

پائتھون کوڈ:

def factorial(n):
          if (n == 0):
              return 1
          else:
              return n * factorial(n - 1)

 

[محب علوی]

اگر n = 4 تو factorial کا فنکشن اس طرح سے چلے گا۔

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

 

[محب علوی]

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

Tree traversal
depth first search
Divide and conquer algorithms



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

 

[عمار نقوی]

محب علوی بھائی مجھے recursion بالکل سمجھ نہیں آرہا۔

 

[محب علوی]

محب علوی بھائی مجھے recursion بالکل سمجھ نہیں آرہا۔

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

Python Recursion