1 00:00:00,000 --> 00:00:07,800 2 00:00:07,800 --> 00:00:10,190 >> ZAMYLA: বুঝতে যাতে recursion, আপনি আবশ্যক 3 00:00:10,190 --> 00:00:13,820 প্রথম recursion বুঝতে. 4 00:00:13,820 --> 00:00:17,280 প্রোগ্রাম ডিজাইন মানে মধ্যে recursion হচ্ছে আপনি স্ব - উল্লেখ আছে 5 00:00:17,280 --> 00:00:18,570 সংজ্ঞা. 6 00:00:18,570 --> 00:00:21,520 Recursive ডাটা স্ট্রাকচার, উদাহরণস্বরূপ, ডাটা স্ট্রাকচার যে 7 00:00:21,520 --> 00:00:23,990 নিজেদের অন্তর্ভুক্ত তাদের সংজ্ঞা. 8 00:00:23,990 --> 00:00:27,160 কিন্তু আজ, আমরা নজর দিতে যাচ্ছেন recursive ফাংশন উপর. 9 00:00:27,160 --> 00:00:31,160 >> , ফাংশন ইনপুট নিতে পুনরাহ্বান যে আর্গুমেন্ট, এবং হিসাবে একটি মান প্রদান করে 10 00:00:31,160 --> 00:00:34,480 দ্বারা প্রতিনিধিত্ব আউটপুট এখানে এই চিত্রটি. 11 00:00:34,480 --> 00:00:38,060 আমরা শরীরের হিসাবে বাক্সের মনে করব সেট ধারণকারী ফাংশন, 12 00:00:38,060 --> 00:00:42,340 ব্যাখ্যা যে নির্দেশাবলী ইনপুট এবং আউটপুট প্রদান. 13 00:00:42,340 --> 00:00:45,660 শরীরের ভেতরে পুরো বিষয়টা বিস্তারিত বিবেচনা গ্রহণ ফাংশন কল প্রকাশ পারে 14 00:00:45,660 --> 00:00:47,430 অন্যান্য কার্যাবলী হিসাবে ভাল. 15 00:00:47,430 --> 00:00:51,300 এই সহজ ফাংশন, foo বিন্যাস, নিন যে ইনপুট হিসেবে একটি একক পংক্তি নেয় এবং 16 00:00:51,300 --> 00:00:54,630 প্রিন্ট কতগুলি অক্ষর যে স্ট্রিং আছে. 17 00:00:54,630 --> 00:00:58,490 স্ট্রিং দ্বারা জন্য ফাংশন strlen,, যার ফলাফল হয়, বলা হয় 18 00:00:58,490 --> 00:01:01,890 printf থেকে কল জন্য প্রয়োজন. 19 00:01:01,890 --> 00:01:05,770 >> এখন, কি একটি recursive ফাংশন তোলে বিশেষ এটি কল নিজেই যে. 20 00:01:05,770 --> 00:01:09,610 আমরা এই recursive উপস্থাপন করতে পারেন এই কমলা তীর কল 21 00:01:09,610 --> 00:01:11,360 ফিরে নিজেকে looping. 22 00:01:11,360 --> 00:01:15,630 কিন্তু আবার নিজেই নির্বাহ শুধুমাত্র ইচ্ছাশক্তি অন্য recursive কল করতে, এবং 23 00:01:15,630 --> 00:01:17,150 অন্য এবং অন্য. 24 00:01:17,150 --> 00:01:19,100 কিন্তু recursive ফাংশন অসীম হতে পারে না. 25 00:01:19,100 --> 00:01:23,490 তারা একরকম শেষ করতে হবে, অথবা আপনার প্রোগ্রাম চিরতরে চালানো হবে. 26 00:01:23,490 --> 00:01:27,680 >> সুতরাং আমরা বিরতি একটি পন্থা খুঁজে বের করতে হবে recursive কল আউট. 27 00:01:27,680 --> 00:01:29,900 আমরা বেস ক্ষেত্রে এই কল. 28 00:01:29,900 --> 00:01:33,570 বেস ক্ষেত্রে শর্ত পূরণ করা হয়, ফাংশন না করে ফেরৎ 29 00:01:33,570 --> 00:01:34,950 অন্য recursive কল. 30 00:01:34,950 --> 00:01:39,610 একটি অকার্যকর ফাংশন, হাই, এই ফাংশন নিন যে ইনপুট হিসাবে কোন int এন লাগে. 31 00:01:39,610 --> 00:01:41,260 বেস কেস আসে প্রথম. 32 00:01:41,260 --> 00:01:46,220 এন কম শূন্য, মুদ্রণ বিদায় এবং যদি অন্য সব ক্ষেত্রে বিনিময়ে, 33 00:01:46,220 --> 00:01:49,400 ফাংশন পরিষ্কার উচ্চ মুদ্রণ ও চালানো হবে recursive কল. 34 00:01:49,400 --> 00:01:53,600 সঙ্গে ফাংশন পরিষ্কার উচ্চ আরেকটি কল একটি decremented ইনপুট মান. 35 00:01:53,600 --> 00:01:56,790 >> এখন, আমরা, HI মুদ্রণ যদিও ফাংশন বিনষ্ট করবে না যে আমরা যতক্ষণ 36 00:01:56,790 --> 00:02:00,370 তার রিটার্ন টাইপ ফিরে, এই ক্ষেত্রে অকার্যকর মধ্যে. 37 00:02:00,370 --> 00:02:04,830 তাই প্রত্যেক এন বেস কেস ছাড়া অন্য জন্য, এই ফাংশন হাই হাই ফিরে আসবে 38 00:02:04,830 --> 00:02:06,890 n এর বিয়োগ 1. 39 00:02:06,890 --> 00:02:10,050 এই ফাংশন যদিও অকার্যকর যেহেতু, আমরা স্পষ্টভাবে এখানে রিটার্ন টাইপ না. 40 00:02:10,050 --> 00:02:12,000 আমরা শুধু ফাংশন নির্বাহ করব. 41 00:02:12,000 --> 00:02:16,960 তাই পরিষ্কার উচ্চ কলিং (3) পরিষ্কার উচ্চ মুদ্রণ ও হবে পরিষ্কার উচ্চ (2) (1) এক পরিষ্কার উচ্চ executes যা চালানো 42 00:02:16,960 --> 00:02:20,560 পরিষ্কার উচ্চ executes যা (0), যেখানে বেস ক্ষেত্রে শর্ত পূরণ করা হয়. 43 00:02:20,560 --> 00:02:24,100 তাই পরিষ্কার উচ্চ (0) বিদায় ছাপে এবং আয়. 44 00:02:24,100 --> 00:02:24,990 >> ঠিক আছে. 45 00:02:24,990 --> 00:02:28,690 তাই এখন আমরা বুনিয়াদি বুঝতে যে তারা প্রয়োজন যে recursive ফাংশন, 46 00:02:28,690 --> 00:02:32,730 অন্তত একটি বেস ক্ষেত্রে যেমন recursive কল, এর একটি যান যাক 47 00:02:32,730 --> 00:02:34,120 আরো অর্থপূর্ণ উদাহরণ. 48 00:02:34,120 --> 00:02:37,830 শুধু ফেরত দেয় না যে এক কোন ব্যাপার কি বাতিলযোগ্য. 49 00:02:37,830 --> 00:02:41,340 >> এর গৌণিক কটাক্ষপাত করা যাক অপারেশন মধ্যে সবচেয়ে বেশি ব্যবহৃত 50 00:02:41,340 --> 00:02:43,660 সম্ভাবনা গণনার. 51 00:02:43,660 --> 00:02:48,120 N এর গুণিতক প্রতি হাজার পণ্য আর ইতিবাচক পূর্ণসংখ্যা কম 52 00:02:48,120 --> 00:02:49,400 ও এন সমান. 53 00:02:49,400 --> 00:02:56,731 সুতরাং গৌণিক পাঁচটি 5 বার 4 বার হল 3 বার 2 বার 1 120 দিতে. 54 00:02:56,731 --> 00:03:01,400 চার গৌণিক 4 বার 3 বার হয় 2 বার 1 24 দিতে. 55 00:03:01,400 --> 00:03:04,910 এবং একই নিয়ম প্রযোজ্য কোন ধনাত্মক পূর্ণসংখ্যা দিতে. 56 00:03:04,910 --> 00:03:08,670 >> তাই কিভাবে আমরা একটি recursive লিখতে পারে গৌণিক হিসাব যে ফাংশন 57 00:03:08,670 --> 00:03:09,960 একটা সংখ্যা? 58 00:03:09,960 --> 00:03:14,700 ভাল, আমরা উভয় শনাক্ত করতে হবে বেস কেস এবং recursive কল. 59 00:03:14,700 --> 00:03:18,250 recursive কল একই হবে বেস ছাড়া সব ক্ষেত্রেই জন্য 60 00:03:18,250 --> 00:03:21,420 কেস, যা আমরা করতে হবে যে মানে আমাদের দিতে হবে এমন একটি প্যাটার্ন খুঁজে আমাদের 61 00:03:21,420 --> 00:03:23,350 কাঙ্ক্ষিত ফলাফল. 62 00:03:23,350 --> 00:03:30,270 >> এই উদাহরণস্বরূপ, কিভাবে 5 গৌণিক দেখুন 1 দ্বারা 2 দ্বারা 3 দ্বারা 4 গুন জড়িত থাকে 63 00:03:30,270 --> 00:03:33,010 এবং যে একই গুণ এখানে পাওয়া যায় 64 00:03:33,010 --> 00:03:35,430 4 গৌণিক সংজ্ঞা. 65 00:03:35,430 --> 00:03:39,810 সুতরাং আমরা 5 গৌণিক যে দেখুন মাত্র 5 বার 4 গৌণিক. 66 00:03:39,810 --> 00:03:43,360 আমি এই প্যাটার্ন প্রয়োগ নেই 4 থেকে পাশাপাশি গুণিতক? 67 00:03:43,360 --> 00:03:44,280 হ্যাঁ. 68 00:03:44,280 --> 00:03:49,120 আমরা 4 গৌণিক ধারণকারী দেখুন গুণন 3 বার 2 বার 1, 69 00:03:49,120 --> 00:03:51,590 3 গৌণিক হিসাবে একই সংজ্ঞা. 70 00:03:51,590 --> 00:03:56,950 তাই 4 গৌণিক 4 বার 3 সমান গৌণিক, এবং তাই এবং তাই ঘোষণা আমাদের 71 00:03:56,950 --> 00:04:02,170 প্যাটার্ন 1 গৌণিক, যতক্ষণ লাঠি যা সংজ্ঞা দ্বারা 1 সমান. 72 00:04:02,170 --> 00:04:04,950 >> অন্য কোন ইতিবাচক আছে ইন্টিজার বাকি. 73 00:04:04,950 --> 00:04:07,870 তাই আমরা জন্য প্যাটার্ন আছে আমাদের recursive কল. 74 00:04:07,870 --> 00:04:13,260 এন গৌণিক এন বার সমান n এর গৌণিক বিয়োগ 1. 75 00:04:13,260 --> 00:04:14,370 এবং আমাদের বেস কেস? 76 00:04:14,370 --> 00:04:17,370 এটা শুধু আমাদের সংজ্ঞা হবেন 1 গৌণিক. 77 00:04:17,370 --> 00:04:19,995 >> তাই এখন আমরা লিখিতভাবে সরানো যাবে ফাংশন জন্য কোড. 78 00:04:19,995 --> 00:04:24,110 বেস কেস জন্য, আমরা করতে হবে শর্ত এন সমান 1, সমান যেখানে 79 00:04:24,110 --> 00:04:25,780 আমরা 1 ফিরে আসবেন. 80 00:04:25,780 --> 00:04:29,280 তারপর recursive কল সম্মুখের চলন্ত, আমরা এন বার ফিরে পাবেন 81 00:04:29,280 --> 00:04:32,180 n এর গৌণিক বিয়োগ 1. 82 00:04:32,180 --> 00:04:33,590 >> এখন আসুন এই আমাদের পরীক্ষা করা যাক. 83 00:04:33,590 --> 00:04:35,900 এর গৌণিক 4 চেষ্টা করুন. 84 00:04:35,900 --> 00:04:39,420 আমাদের ফাংশন প্রতি এটি সমান 4 বার গৌণিক থেকে (3). 85 00:04:39,420 --> 00:04:43,040 গুণিতক (3) সমান 3 বার গৌণিক (2). 86 00:04:43,040 --> 00:04:48,700 গুণিতক (2) 2 বার সমান গৌণিক (1), যা 1 প্রদান. 87 00:04:48,700 --> 00:04:52,490 গুণিতক (2) এখন 2 বার 1, 2 ফেরৎ. 88 00:04:52,490 --> 00:04:55,960 গুণিতক (3) এখন ফিরে আসতে পারেন 3 বার 2, 6. 89 00:04:55,960 --> 00:05:02,490 এবং পরিশেষে, গৌণিক (4) 4 বার 6, 24 ফেরৎ. 90 00:05:02,490 --> 00:05:06,780 >> আপনার কোন অসুবিধা সম্মুখীন করছেন recursive কল সঙ্গে, যে সাজা 91 00:05:06,780 --> 00:05:09,660 ফাংশন ইতিমধ্যে কাজ করে. 92 00:05:09,660 --> 00:05:13,450 আমি কি এই দ্বারা মানে হল আপনি উচিত যে ফিরে আপনার recursive কল বিশ্বাস 93 00:05:13,450 --> 00:05:15,100 সঠিক মান. 94 00:05:15,100 --> 00:05:18,960 উদাহরণস্বরূপ, আমি যদি জানেন যে গৌণিক (5) 5 বার সমান 95 00:05:18,960 --> 00:05:24,870 গৌণিক (4), আমি যে বিশ্বাস করা যাচ্ছে না গৌণিক (4) আমার 24 দিতে হবে. 96 00:05:24,870 --> 00:05:28,510 আপনি যদি একটি পরিবর্তনশীল হিসাবে মনে করে করবে না, আপনার আগে থেকেই নির্ধারিত হলে 97 00:05:28,510 --> 00:05:30,070 গৌণিক (4). 98 00:05:30,070 --> 00:05:33,850 সুতরাং কোনো গৌণিক জন্য (ঢ), এটা n এর পণ্য এবং 99 00:05:33,850 --> 00:05:35,360 পূর্ববর্তী গৌণিক. 100 00:05:35,360 --> 00:05:38,130 এবং এই আগের গৌণিক কল করে প্রাপ্ত হয় 101 00:05:38,130 --> 00:05:41,330 n এর গৌণিক বিয়োগ 1. 102 00:05:41,330 --> 00:05:45,130 >> আপনি বাস্তবায়ন করতে পারেন এখন, যদি দেখতে একটি recursive নিজের কাজ. 103 00:05:45,130 --> 00:05:50,490 আপনার টার্মিনাল আপ লোড করুন, অথবা run.cs50.net, এবং একটি ফাংশন যোগফল লিখুন 104 00:05:50,490 --> 00:05:54,770 যে একটি পূর্ণসংখ্যা এন নেয় এবং ফেরৎ সব পরপর ইতিবাচক ও যোগফল 105 00:05:54,770 --> 00:05:57,490 এন থেকে 1 থেকে ইন্টিজার. 106 00:05:57,490 --> 00:06:01,000 আমি কিছু অঙ্কের আউট লিখিত করেছি আপনি সাহায্য মান আমাদের. 107 00:06:01,000 --> 00:06:04,030 প্রথমত, চিন্তা করা বেস ক্ষেত্রে শর্ত. 108 00:06:04,030 --> 00:06:06,170 এর পরে, যোগফল তাকান (5). 109 00:06:06,170 --> 00:06:09,270 আপনি পরিপ্রেক্ষিতে তা প্রকাশ করতে পারেন অন্য সমষ্টি? 110 00:06:09,270 --> 00:06:11,290 এখন, কি যোগফল সম্পর্কে (4)? 111 00:06:11,290 --> 00:06:15,630 আপনি কিভাবে যোগফল প্রকাশ করতে পারেন (4) অন্য যোগফল পরিপ্রেক্ষিতে? 112 00:06:15,630 --> 00:06:19,655 >> আপনি যোগফল একবার (5) ও যোগফল (4) অন্যান্য অঙ্কের নিরিখে প্রকাশ করেন, দেখতে 113 00:06:19,655 --> 00:06:22,970 আপনি একটি চিহ্নিত করতে পারেন যোগফল (ঢ) জন্য প্যাটার্ন. 114 00:06:22,970 --> 00:06:26,190 যদি না হয়, কয়েক অন্যান্য সংখ্যার চেষ্টা এবং তাদের অঙ্কের মধ্যে প্রকাশ 115 00:06:26,190 --> 00:06:28,410 অন্য সংখ্যার নিরিখে. 116 00:06:28,410 --> 00:06:31,930 বিযুক্ত জন্য নিদর্শন চিহ্নিত করে সংখ্যা, আপনি আপনার পথ থেকে ভাল আছেন 117 00:06:31,930 --> 00:06:34,320 কোনো ঢ জন্য প্যাটার্ন চিহ্নিত. 118 00:06:34,320 --> 00:06:38,040 >> Recursion সত্যিই একটি শক্তিশালী হাতিয়ার, তাই অবশ্যই এটি সীমাবদ্ধ নয় 119 00:06:38,040 --> 00:06:39,820 গাণিতিক ফাংশন. 120 00:06:39,820 --> 00:06:44,040 Recursion খুব কার্যকরভাবে ব্যবহার করা যাবে উদাহরণস্বরূপ গাছ সঙ্গে যখন কারবারী. 121 00:06:44,040 --> 00:06:47,210 একটি জন্য গাছ ছোট দেখুন আরো পুঙ্খানুপুঙ্খ পর্যালোচনা, কিন্তু এখন জন্য 122 00:06:47,210 --> 00:06:51,140 , যে বাইনারি অনুসন্ধান গাছ প্রত্যাহার বিশেষ ব্যবহারের প্রতি, নোড আপ করা হয় 123 00:06:51,140 --> 00:06:53,820 একটি মান এবং দুই নোড পয়েন্টার দিয়ে. 124 00:06:53,820 --> 00:06:57,270 সাধারণত, এই প্রতিনিধিত্ব করেন এক লাইন প্রতি নির্দেশ থাকার মূল নোড 125 00:06:57,270 --> 00:07:01,870 বাম সন্তানের নোড এবং এক ডান সন্তানের নোডের. 126 00:07:01,870 --> 00:07:04,510 একটি বাইনারি অনুসন্ধান গঠন গাছ নিজেই ভাল ধার 127 00:07:04,510 --> 00:07:05,940 একটি recursive সার্চ করতে. 128 00:07:05,940 --> 00:07:09,730 recursive কল মধ্যে পাসের বাম বা ডান নোড, কিন্তু আরও 129 00:07:09,730 --> 00:07:10,950 গাছ সংক্ষেপে যে. 130 00:07:10,950 --> 00:07:15,690 >> আপনার উপর একটি অপারেশন সম্পাদন করতে চান বলুন একটি বাইনারি ট্রি মধ্যে প্রতি একক নোড. 131 00:07:15,690 --> 00:07:17,410 আপনি কিভাবে যে সম্পর্কে যেতে পারে? 132 00:07:17,410 --> 00:07:20,600 হ্যাঁ, আপনি একটি recursive লিখতে পারেন অপারেশন সঞ্চালিত ফাংশন 133 00:07:20,600 --> 00:07:24,450 ঊর্ধ্বতন নোডের উপর এবং একটি recursive করে তোলে একই ফাংশন কল, 134 00:07:24,450 --> 00:07:27,630 বাম পাশ করার এবং ডান সন্তানের নোড. 135 00:07:27,630 --> 00:07:31,650 উদাহরণস্বরূপ, এই ফাংশন, foo বিন্যাস, যে একটি নির্দিষ্ট নোড এর মান এবং পরিবর্তন 136 00:07:31,650 --> 00:07:33,830 1 তার সন্তানদের সব. 137 00:07:33,830 --> 00:07:37,400 একটি নাল নোড কারণ বেস কেস ফাংশন ইঙ্গিত, ফিরে যাও 138 00:07:37,400 --> 00:07:41,290 কোনো নোড আছে না যে যে সাব - ট্রি বাকি. 139 00:07:41,290 --> 00:07:42,620 >> এর এটা ভিতর দিয়ে হেটে যাক. 140 00:07:42,620 --> 00:07:44,340 প্রথম ঊর্ধ্বতন 13 হয়. 141 00:07:44,340 --> 00:07:47,930 আমরা 1 থেকে মান পরিবর্তন, এবং তারপর কল আমাদের বাম ফাংশন হিসাবে ভাল 142 00:07:47,930 --> 00:07:49,600 সঠিক হিসাবে. 143 00:07:49,600 --> 00:07:53,910 ফাংশন, foo বিন্যাস, বাম বলা হয় প্রথম সাব - ট্রি, তাই বাম নোড 144 00:07:53,910 --> 00:07:57,730 1 এবং foo বিন্যাস করতে পুনরায় নির্ধারণ করা হবে যে নোড এর শিশুদের আহ্বান করা, 145 00:07:57,730 --> 00:08:01,900 প্রথম বাম এবং তারপর ডান, এবং তাই এবং তাই ঘোষণা. 146 00:08:01,900 --> 00:08:05,630 এবং শাখা নেই তাদের বলুন কোন শিশু যাতে একই প্রক্রিয়া 147 00:08:05,630 --> 00:08:09,700 ডান শিশুদের জন্য অব্যাহত থাকবে পুরো গাছ এর নোড পর্যন্ত 148 00:08:09,700 --> 00:08:11,430 1 থেকে পুনরায় নির্ধারণ. 149 00:08:11,430 --> 00:08:15,390 >> যেহেতু আপনি দেখতে পারেন, আপনি সীমাবদ্ধ নয় শুধু একটা recursive কল. 150 00:08:15,390 --> 00:08:17,930 কাজ শেষ হবে শুধু হিসাবে অনেক. 151 00:08:17,930 --> 00:08:21,200 আপনি একটি গাছ ছিল কি যদি যেখানে প্রতিটি নোড তিনটি সন্তান ছিল, 152 00:08:21,200 --> 00:08:23,100 বাম, মধ্যম, এবং ডান? 153 00:08:23,100 --> 00:08:24,886 আপনি কিভাবে foo বিন্যাস সম্পাদনা করতে চান? 154 00:08:24,886 --> 00:08:25,860 ভাল, সহজ. 155 00:08:25,860 --> 00:08:30,250 শুধু অন্য recursive কল যোগ করা এবং মাঝখানে নোড পয়েন্টার পাস. 156 00:08:30,250 --> 00:08:34,549 >> Recursion খুব শক্তিশালী এবং না করা হয় মার্জিত উল্লেখ, কিন্তু এটি একটি হতে পারে 157 00:08:34,549 --> 00:08:38,010 প্রথমে কঠিন ধারণা, তাই হতে রোগী এবং আপনার সময় লাগবে. 158 00:08:38,010 --> 00:08:39,370 বেস কেস দিয়ে শুরু করুন. 159 00:08:39,370 --> 00:08:42,650 এটি সাধারণত চিহ্নিত সহজে, এবং তারপর আপনি কাজ করতে পারেন 160 00:08:42,650 --> 00:08:43,830 পিছন দিকে সেখানে থেকে. 161 00:08:43,830 --> 00:08:46,190 আপনি পৌঁছানোর প্রয়োজন জানেন আপনার বেস কেস, তাই যে যথাসাধ্য 162 00:08:46,190 --> 00:08:47,760 আপনি কয়েক নির্দেশ দিতে. 163 00:08:47,760 --> 00:08:53,120 এক নির্দিষ্ট ক্ষেত্রে প্রকাশ করার চেষ্টা করুন অন্যান্য ক্ষেত্রে শর্ত, অথবা উপ - কেতা. 164 00:08:53,120 --> 00:08:54,700 >> এই ছোট দেখার জন্য ধন্যবাদ. 165 00:08:54,700 --> 00:08:58,920 অন্ততপক্ষে, এখন আপনি করতে পারেন ভালো ঢামালি বুঝতে. 166 00:08:58,920 --> 00:09:01,250 আমার নাম Zamyla, এবং এই CS50 হয়. 167 00:09:01,250 --> 00:09:04,306 168 00:09:04,306 --> 00:09:07,170 >> হাই, এই ফাংশন নিয়ে যান, একটি লাগে অকার্যকর ফাংশন 169 00:09:07,170 --> 00:09:09,212 কোন int, এন, ইনপুট হিসেবে. 170 00:09:09,212 --> 00:09:11,020 বেস কেস আসে প্রথম. 171 00:09:11,020 --> 00:09:14,240 এন কম 0, মুদ্রণ যদি "বিদায়" এবং বিনিময়ে. 172 00:09:14,240 --> 00:09:15,490