[موسیقی بجانے] 

ڈوگ لایڈ: آپ نے شاید لگتا ہے کہ کوڈ کو صرف ایک کام کو پورا کرنے کے لئے استعمال ہے. تم نے اسے لکھنے. یہ کچھ کرتا ہے. اس سے بہت زیادہ ہے. 

آپ نے اسے مرتب. آپ پروگرام چلاتے ہیں. تم جانا اچھا ہو. 

لیکن یہ یقین ہے یا نہیں، تو آپ کو ایک طویل وقت کے لئے کوڈ آپ اصل کو دیکھنے کے لئے آ سکتا ہے خوبصورت ہے کہ کچھ کے طور پر کوڈ. یہ ایک مسئلہ میں حل ایک بہت ہی دلچسپ طریقہ، یا واقعی صرف وہاں کچھ ہے یہ لگتا ہے جس طرح کے بارے میں صاف. تم ہںس کیا جا سکتا ہے مجھ پر، لیکن یہ سچ ہے. اور تکرار ایک طریقہ ہے قسم کے اس خیال حاصل کرنے کے لئے خوبصورت، خوبصورت نظر کوڈ. یہ طریقوں سے مسائل حل کرتی ہے کہ ، دیکھ کرنے کے لئے آسان، دلچسپ ہیں اور حیرت کی بات مختصر. 

راستہ تکرار کام ایک پنراورتی تقریب، ہے بلاتا ہے کہ ایک تقریب کے طور پر بیان کیا جاتا ہے خود اس پر عملدرآمد کے حصے کے طور. یہ ایک چھوٹا سا عجیب لگتا ہے ہو سکتا اور ہم تھوڑا سا نظر آئے گا اس ایک لمحے میں کس طرح کام کرتا. لیکن ایک بار پھر، ان پنراورتی طریقہ کار ہیں اتنا خوبصورت ہونے جا رہا وہ جا رہے ہیں کیونکہ بغیر اس مسئلے کو حل کرنے ان تمام دیگر افعال ہونے یا ان طویل loops کے. تم ان پنراورتی دیکھیں گے کہ طریقہ کار اتنی مختصر دیکھنے کے لئے جا رہے ہیں. اور وہ واقعی بنانے کے لئے جا رہے ہیں اپنے کوڈ کو بہت زیادہ خوبصورت لگ رہی ہو. 

میں آپ کو ایک مثال دیتا ہوں اس کی کس طرح دیکھنے کے لئے ایک پنراورتی طریقہ کار بیان کیا جا سکتا ہے. آپ کو اس سے واقف ہیں تو ، کئی سال پہلے ریاضی کی کلاس سے وہاں کچھ کہا جاتا ہے عام طور پر ہے جو جز ضربیہ تقریب، فجائیہ نقطہ، کے طور پر ظاہر کیا جاتا ہے جس تمام مثبت صحیح عدد سے زیادہ بیان کیا جاتا ہے. اور جس طرح کہ (ن) جز ضربیہ شمار کیا جاتا ہے آپ سب ضرب ہے مقابلے کی تعداد کم یا برابر N together-- سے تمام integers کے مقابلے میں کم یا ایک ساتھ (ن) کے برابر. 

لہذا 5 جز ضربیہ 5 بار ہے 4 اوقات 3 بار 2 بار 1. اور 4 جز ضربیہ 4 گنا زیادہ ہے 3 بار 2 بار 1 اور اسی طرح. آپ کو اندازہ ہو. 

پروگرامر کے طور پر، ہم ایسا نہیں کرتے (ن)، فجائیہ نقطہ استعمال. تو ہم جز ضربیہ کی وضاحت کریں گے (ن) کی حقیقت کے طور پر تقریب. اور ہم پیدا کرنے کے جز ضربیہ کا استعمال کریں گے ایک مسئلہ ایک پنراورتی حل. اور میں آپ کو مل سکتا ہے یہ ایک بہت زیادہ ضعف ہے کہ تکراری سے اپیل اس کا ورژن، جس ہم بھی ایک لمحے میں ایک نظر ڈالیں گے. 

تو یہاں کے ایک جوڑے ہیں facts-- شلیش ارادہ کے بارے میں factorial-- جز ضربیہ تقریب. میں نے کہا کہ 1 جز ضربیہ،، 1 ہے. 2 جز ضربیہ 2 بار 1. 3 جز ضربیہ 3 2 مرتبہ اسی اوقات 1، اور. ہم نے پہلے ہی 4 اور 5 کے بارے میں بات. 

لیکن یہ دیکھ کر، یہ سچ نہیں ہے؟ 2 جز ضربیہ نہیں ہے صرف 2 بار 1 جز ضربیہ؟ میرا مطلب ہے، 1 جز ضربیہ 1 ہے. تو کیوں نہ ہم صرف کا کہنا ہے کہ نہیں کر سکتے ہیں، 2 جز ضربیہ 2 بار 1 ہے کے بعد سے، یہ واقعی صرف 2 بار ہے 1 جز ضربیہ؟ 

اور پھر، اس خیال میں توسیع 3 جز ضربیہ نہیں ہے صرف 3 بار 2 جز ضربیہ؟ اور 4 جز ضربیہ 4 گنا زیادہ ہے تو 3، اور جز ضربیہ؟ اصل میں، جز ضربیہ کسی بھی تعداد کے صرف کر سکتے ہیں قسم اگر ہم اظہار کیا کے ہمیشہ کے لئے اس سے باہر لے جانے. ہم اس قسم کی عام کر سکتے ہیں جز ضربیہ مسئلہ یہ ہے کے طور پر (ن) بار ن مائنس 1 جز ضربیہ. یہ (ن) بار مصنوعات کی ہے تمام اعداد و شمار مجھ سے کم. 

یہ خیال، اس مسئلے کا سامانییکرن، ہم تکراری کرنے کی اجازت دیتا جز ضربیہ تقریب کی وضاحت. آپ کو ایک تقریب کی وضاحت جب تکراری طور پر، وہاں ہے اس کا ایک حصہ بننے کے لئے کی ضرورت ہے کہ دو چیزیں. تم کچھ ایک نام نہاد حاصل کرنے کی ضرورت بنیاد کیس، جس میں، آپ کو اس متحرک جب، پنراورتی عمل کو روک دے گا. 

دوسری صورت میں، ایک تقریب جو بلاتا ہے itself-- آپ imagine-- سکتا ہے ہمیشہ کے لئے پر جا سکتے ہیں. تقریب بلاتا ہے تقریب کالیں تقریب بلاتا ہے. آپ کو ایک راستہ نہیں ہے تو ، آپ کے پروگرام کو روکنے کے لئے مؤثر طریقے سے پھنس جائے گا ایک لامتناہی لوپ میں. یہ، آخر میں کریش گا یہ میموری سے باہر چلانے گا کیونکہ. لیکن اس نقطہ نظر کے سوا ہے. 

ہم کو روکنے کے لئے کسی دوسرے طریقے سے حاصل کرنے کی ضرورت ہمارے پروگرام اجلاس ہونے کے تناظر کے علاوہ چیزیں، کریش کہ ایک پروگرام ہے کیونکہ شاید خوبصورت یا خوبصورت نہیں. اور ہم اس کی بنیاد کیس کہتے ہیں. یہ ایک آسان حل ہے رک جاتا ہے جس میں ایک مسئلے سے واقع ہونے سے پنراورتی عمل. تو اس میں سے ایک حصہ ہے ایک پنراورتی تقریب. 

دوسرا حصہ پنراورتی معاملہ ہے. یہ جہاں تکرار ہے اصل میں جگہ لے جائے گا. یہ ہے جہاں تقریب میں خود کو فون کروں گا. 

یہ بالکل میں خود فون نہیں کرے گا اسی طرح یہ کہا گیا تھا. یہ تھوڑا سا مختلف حالتوں کو ہو گا یہ بات ہے مسئلہ ہے ایک teeny سا چھوٹا حل کرنے کی کوشش. لیکن یہ عام طور پر ہرن گزر کے حل کا بڑا حصہ حل کی لکیر سے نیچے ایک مختلف کال کرنے کے لئے. 

ان میں سے کون سا لگتا ہے یہاں بنیاد کیس کی طرح؟ جس طرح ان میں سے ایک لگتا ہے ایک مسئلہ کرنے کا آسان ترین حل کیا ہے؟ ہم factorials کے کا ایک گروپ ہے، اور ہم جاری کر سکتے ہیں اسی on-- 6، 7، 8، 9، 10، اور جا. 

لیکن ایک طرح ان میں سے ایک لگتا ہے اچھا معاملہ بنیاد کیس ہونے کے لئے. یہ ایک بہت آسان حل ہے. ہم خصوصی کچھ بھی کرنے کی ضرورت نہیں. 

1 جز ضربیہ صرف 1 ہے. ہم کسی کو ایسا کرنے کی ضرورت نہیں ہے ضرب بالکل. ہم جا رہے ہیں تو ایسا لگتا ہے کوشش کریں اور اس مسئلہ کو حل کرنے، اور ہم کو روکنے کے لئے کی ضرورت ہے کہیں تکرار، ہم شاید کو روکنے کے لئے چاہتے ہیں یہ ہم 1 حاصل کرنے کے لئے جب. ہم اس سے پہلے روکنے کے لئے نہیں کرنا چاہتا. 

ہم وضاحت کر رہے ہیں تو اپنے جز ضربیہ تقریب، یہاں ایک کنکال کے لئے ہے ہم ایسا ہو سکتا ہے کہ کس طرح. ہم ان دو چیزوں میں پلگ کرنے کی ضرورت بنیاد کیس اور پنراورتی کیس. بنیاد کیس کیا ہے؟ N 1 سے برابر ہے تو واپسی 1-- ہے ایک بہت سادہ مسئلہ کو حل کرنے. 

1 جز ضربیہ 1 ہے. یہ 1 اوقات کچھ ہے. یہ صرف 1 ہے. یہ ایک بہت آسان حقیقت ہے. اور تو ہے کہ ہماری بنیاد کیس ہو سکتا ہے. ہم اس میں 1 منظور ہو تو تقریب، ہم نے صرف 1 واپس آ جائیں گے. 

پنراورتی کیا ہے کیس شاید طرح نظر آتے ہیں؟ ہر دوسرے نمبر کے لئے 1 اس کے علاوہ، پیٹرن کیا ہے؟ ٹھیک ہے، ہم لے جا رہے ہیں تو (ن) کے جز ضربیہ، یہ (ن) اوقات (ن) کے جز ضربیہ مائنس 1. 

ہم 3 جز ضربیہ لے جا رہے ہیں تو، یہ 3 مائنس 1 میں 3 بار جز ضربیہ ہے یا 2. اور ہم نہیں ہیں اگر ایسا ہے تو دوسری صورت میں، 1 تلاش واپسی (ن) بار ن مائنس 1 جز ضربیہ. یہ بہت سیدھا ہے. 

اور تھوڑا سا ہونے کی خاطر کلینر اور کوڈ سے زیادہ خوبصورت، جانتے ہیں کہ ہم ایک لائن loops ہے اگر یا سنگل لائن مشروط شاخوں، ہم میں سے سب سے چھٹکارا حاصل کر سکتے ہیں ان کے ارد گرد گھوبگھرالی منحنی خطوط وحدانی. تو ہم اس کے لیے اس کو مضبوط بنانے کے کر سکتے ہیں. یہ بالکل ایک ہی ہے اس کے طور پر فعالیت. 

میں صرف گھوبگھرالی دور لے جا رہا ہوں صرف ایک ہی لائن ہے کیونکہ، منحنی خطوط وحدانی ان مشروط شاخوں کے اندر. تو ان شناختی برتاؤ. N 1 سے برابر ہے تو، 1 واپس. ورنہ N اوقات واپس ن مائنس 1 جز ضربیہ. تو ہم چھوٹے مسئلہ بنا رہے ہیں. N 5 کے طور پر باہر شروع ہوتا ہے، ہم جا رہے ہیں 4 5 بار جز ضربیہ واپس. اور ہم بات کرتے ہیں ایک منٹ میں دیکھیں گے ایک اور ویڈیو میں کال stack-- بارے میں جہاں ہم کے بارے میں بات ہم سیکھنے گے stack-- کال بالکل اس عمل کام کرتا ہے کیوں کے بارے میں. 

لیکن اس کی 5 جبکہ جز ضربیہ کا کہنا ہے کہ 5 بار جز ضربیہ 4 کی واپسی، اور 4 اچھی طرح سے، ٹھیک ہے، کا کہنا ہے کہ جا رہا ہے، کی واپسی 4 بار 3 جز ضربیہ. آپ دیکھ سکتے ہیں کے طور پر، ہم ہیں قسم 1 کے قریب. ہم قریب ہو رہی ہے اور اس کی بنیاد کیس کے قریب. 

اور ہم بنیاد کیس مارا ایک بار، گزشتہ افعال میں سے سب انہوں نے کے لئے تلاش کر رہے تھے جواب ہے. 2 جز ضربیہ کی واپسی کہہ رہا تھا 2 بار 1 جز ضربیہ. ویسے، 1 ریٹرن 1 جز ضربیہ. جز ضربیہ کے لئے تو کال 2، 2 بار 1 واپس آ سکتے ہیں اور جز ضربیہ ہے کہ واپس دینے کے اس کے نتیجے کے لئے انتظار کر رہا ہے جس میں 3،. 

اور پھر یہ حساب کر سکتے ہیں اس کا نتیجہ، 3 بار 2، 6 اور 4 جز ضربیہ لئے اسے واپس دے. اور پھر، ہم ایک ہیں کال اسٹیک پر ویڈیو یہ ایک چھوٹا سا سچتر ہے جہاں میں ابھی کیا کہہ رہا ہوں کے مقابلے میں زیادہ. لیکن یہ بات ہے. یہ اکیلے کا حل ہے ایک بڑی تعداد کے جز ضربیہ حساب. 

یہ کوڈ کا صرف چار لائنوں ہے. یہ ٹھیک ہے، بہت اچھا ہے؟ یہ شہوانی، شہوت انگیز کی طرح ہے. 

تو عام طور پر، لیکن نہیں ہمیشہ، ایک پنراورتی تقریب ایک میں ایک لوپ جگہ لے سکتے ہیں غیر پنراورتی تقریب. تو یہاں، شانہ بہ شانہ، تکراری ہے جز ضربیہ تقریب کے ورژن. ان دونوں کا حساب بالکل ایک ہی بات. 

وہ دونوں (ن) کے جز ضربیہ حساب. بائیں پر ورژن ایسا کرنے کے لئے تکرار استعمال کرتا ہے. دائیں ورژن ایسا کرنے کے لئے تکرار استعمال کرتا ہے. 

اور نوٹس، ہم اعلان کرنا ہوگا ایک عددی کی مصنوعات کو ایک متغیر. اور پھر ہم لوپ. جب تک کے طور پر ہم ن، زیادہ 0 ہے (ن) کی طرف سے اس کی مصنوعات کو ضرب رکھنے اور جب تک این decrementing ہم نے مصنوعات کے حساب. تو ان دو افعال، ایک بار پھر، بالکل ایک ہی بات کرتے ہیں. لیکن وہ ایسا نہیں کرتے بالکل اسی طرح. 

اب، یہ ممکن ہے ایک سے زیادہ کی بنیاد ہے کیس یا ایک سے زیادہ پنراورتی کیس، منحصر ہے کیا آپ کی تقریب میں کرنے کی کوشش کر رہا ہے. آپ کو لازمی طور صرف تک محدود نہیں کر رہے ہیں ایک بنیاد کیس یا ایک پنراورتی معاملہ. کچھ کے بارے میں تو ایک مثال کے طور پر ایک سے زیادہ بیس مقدمات کے ساتھ ہو سکتا ہے this-- فبونیکی تعداد ترتیب. 

آپ کی طرف سے یاد کر سکتے ہیں ابتدائی اسکول کے دنوں فبونیکی ترتیب بیان کیا جاتا ہے کہ this-- طرح پہلے عنصر 0. دوسرا عنصر 1 ہے. ان میں سے دونوں صرف تعریف کی طرف سے ہیں. 

پھر ہر دوسرے عنصر بیان کیا جاتا ہے ن مائنس 1 اور ن مائنس 2 کی رقم کے طور پر. تیسرا عنصر تو 0 علاوہ 1 1 ہے ہو جائے گا. اور پھر چوتھا عنصر دوسرا عنصر، 1 ہو جائے گا، علاوہ تیسرا عنصر، 1. اس 2 ہو جائے گا. اور اسی طرح اور اسی طرح. 

تو اس صورت میں، ہم نے دو کی بنیاد مقدمات ہیں. N 1 سے برابر ہے تو، 0 واپس. N 2 کے برابر ہے تو، 1 واپس. دوسری صورت میں، (ن) کے فبونیکی واپس مائنس 1 پلس ن مائنس 2 فبونیکی. 

تو اس سے زیادہ بیس مقدمات ہے. کیا ایک سے زیادہ پنراورتی مقدمات کے بارے میں؟ ویسے، وہاں کچھ ہے Collatz اٹکل بلایا. میں، کا کہنا ہے کہ نہیں کر رہا ہوں آپ، یہ ہے کہ کیا معلوم یہ اصل میں ہمارے حتمی ہے کیونکہ یہ خاص طور پر ویڈیو کے لئے مسئلہ. اور یہ ہمارے ورزش ہے ایک دوسرے کے ساتھ پر کام کرنے کے. 

تو یہاں کیا ہے Collatz اٹکل is-- یہ ہر مثبت عدد صحیح پر لاگو ہوتا ہے. اور یہ ہے کہ speculates کے ہمیشہ ممکن واپس حاصل کرنے کے 1 آپ ان اقدامات پر عمل کریں تو. N 1 ہے، کو روکنے کے. N 1 ہے تو ہم 1 واپس مل گیا ہے. 

دوسری صورت میں، اس کے ذریعے جانے عمل پھر ن 2 سے تقسیم. آپ 1 کو واپس حاصل کر سکتے ہیں اور دیکھو. (ن) عجیب ہے تو دوسری صورت میں،، کے ذریعے جانا پھر 3N پلس 1 پر اس عمل کو، یا 3 اوقات (ن) کے علاوہ 1. تو یہاں ہم ایک بنیاد کیس ہے. N 1 سے برابر ہے تو، کو روکنے کے. ہم کسی بھی زیادہ تکرار نہیں کر رہے ہیں. 

لیکن ہم دو پنراورتی مقدمات ہیں. (ن) بھی ہے تو، ہم ایک پنراورتی کرتے کیس، ن 2 سے تقسیم بلا. (ن) عجیب ہے تو، ہم ایک مختلف کرنا 3 اوقات (ن) کے علاوہ 1 پنراورتی کیس. 

اور اس طرح یہ ویڈیو کے لئے مقصد ہے ، ایک دوسرے کے لے ویڈیو کو روکنے کے لئے، اور کوشش کریں اور یہ لکھیں پنراورتی تقریب Collatz تم کہاں، ایک قدر ن میں منتقل اور یہ کتنے قدم یہ حساب لگاتا ہے آپ (ن) کی طرف سے شروع کرتے ہیں تو 1 حاصل کرنے کے لئے لیتا ہے اور آپ کے اوپر ان اقدامات پر عمل کریں. N 1 ہے تو، یہ 0 اقدامات. دوسری صورت میں، یہ جا رہا ہے تاہم ایک قدم کے علاوہ لے یہ یا تو (ن) پر لے جاتا ہے کئی اقدامات 2 سے تقسیم ن بھی ہے، یا 3N پلس 1 تو (ن) عجیب ہے. 

اب، میں یہاں کی سکرین پر ڈال دیا آپ کے لئے ٹیسٹ چیزوں کے ایک جوڑے، آپ کے لئے ٹیسٹ مقدمات کی ایک جوڑے، کو دیکھنے کے لئے ان مختلف Collatz تعداد ہیں، اور یہ بھی ایک مثال اقدامات کی کہ تو آپ کر سکتے ہیں کے ذریعے چلا گیا کیا جا کرنے کی ضرورت ہے قسم کی کارروائی میں اس عمل کو دیکھنے. (ن) کے برابر ہے تو 1، (ن) کے Collatz 0. تمہیں کیا کرنا ہے نہیں ہے کچھ 1 کو واپس حاصل کرنے. آپ نے پہلے ہی وہاں ہو. 

ن 2 ہے تو، یہ لیتا ہے ایک مرحلہ نمبر 1 حاصل کرنے کے لئے. آپ کو 2 کے ساتھ شروع. ویسے، 2 1 کے برابر نہیں ہے. تو یہ ایک قدم جا رہا ہے علاوہ تاہم بہت سے قدم یہ پر لیتا ن 2 سے تقسیم. 

2 سے تقسیم 2 1 ہے. تو یہ تاہم ایک قدم کے علاوہ لیتا بہت سے اقدامات 1 کے لئے لیتا ہے. 1 صفر اقدامات. 

آپ دیکھ سکتے ہیں کے طور پر 3 کے طور پر، وہاں ہے بہت چند قدم ملوث. آپ 3 سے چلے جاؤ. اور پھر آپ کے پاس جاؤ 10، 5، 16، 8، 4، 2، 1. 1 کو واپس حاصل کرنے سات اقدامات. آپ دیکھ سکتے ہیں کے طور پر، وہاں ایک یہاں جوڑے دیگر ٹیسٹ کے مقدمات آپ کے پروگرام کے باہر کی جانچ کرنے کے لئے. تو ایک بار پھر، ویڈیو کو روکنے کے. اور مجھے اب واپس کود جائیں گے اصل عمل یہاں کیا، قیاس ہے. 

آپ کو پتہ کر سکتے ہیں دیکھو (ن) کے Collatz کی وضاحت کرنے کے لئے کس طرح یہ کتنے کا حساب لگاتا ہے تاکہ 1 حاصل کرنے کے لئے لیتا ہے اقدامات. تو امید ہے کہ، آپ کو ویڈیو کو روک دیا ہے اور آپ کو صرف میرے لئے انتظار کر رہے ہیں نہیں کر رہے ہیں یہاں آپ کو جواب دینے کے لئے. لیکن اگر آپ اچھی طرح سے، یہاں جواب ویسے بھی ہے. 

تو یہاں ایک ممکنہ تعریف ہے Collatz تقریب کی. (ن) ہے تو ہماری بنیاد case-- 1 سے برابر، ہم 0 واپس. یہ کسی بھی لے نہیں ہے اقدامات 1 کو واپس حاصل کرنے. 

دوسری صورت میں، ہم نے دو پنراورتی cases-- ہے بھی تعداد کے لئے ایک اور عجیب کے لئے ایک. میں بھی تعداد کے لئے ٹیسٹ طریقہ ن جدید 2 0 کے برابر ہے تو جانچ پڑتال کرنے کے لئے ہے. یہ، ایک بار پھر، بنیادی طور پر ہے سوال پوچھ، تم کیا جدید is-- یاد اگر میں 2 کی طرف سے تقسیم (ن) کوئی باقی ہے؟ کہ اس سے بھی بڑی تعداد ہو جائے گا. 

اور تو (ن) جدید 2 0 برابر ہے ٹیسٹنگ اس سے بھی بڑی تعداد ہے. اگر ایسا ہے تو، میں نے 1 واپس کرنا چاہتے ہیں، یہ یقینی طور پر ہے کیونکہ ایک قدم کے علاوہ Collatz لینے جو کچھ بھی نمبر مجھ سے نصف ہے. دوسری صورت میں، میں نے 1 واپس کرنا چاہتے ہیں علاوہ Collatz کے 3 اوقات (ن) کے علاوہ 1. کہ دوسرے تھا پنراورتی قدم ہے کہ ہم حساب کرنے لگ سکتا ہے اقدامات کی تعداد Collatz-- اسے واپس حاصل کرنے کے لئے لیتا 1 ایک نمبر دیا. تو امید ہے کہ، اس مثال آپ کو تھوڑا سا دیا پنراورتی طریقہ کار کی ایک ذائقہ. امید ہے، آپ کو کوڈ ہے تھوڑا زیادہ تو خوبصورت لاگو ایک خوبصورت، پنراورتی انداز میں. بھی نہیں لیکن اگر، تکرار ہے بہر حال واقعی طاقتور آلہ. اور اس طرح یہ یقینی طور پر کچھ ہے ارد گرد اپنے سر حاصل کرنے کے لئے، آپ کو بنانے کے لئے قابل ہو جائے گا، کیونکہ تکرار استعمال بہت اچھا پروگرام کہ دوسری صورت میں لکھنے کے لئے پیچیدہ ہو سکتا ہے آپ loops اور iteration کے استعمال کر رہے ہیں. میں ڈوگ لایڈ ہوں. یہ CS50 ہے.