دانلود آنی و ارسال سریع
در ریاضیات، رابطه بازگشتی (Recurrence Relation)، دنباله ای است که به صورت بازگشتی تعریف می شود. در یک دنباله بازگشتی، یک معادله به نام رابطه بازگشتی ارائه می شود که با آن، جمله n ام دنباله به جملات پیشین مرتبط می شود. مقادیر چند جمله اول دنباله به نام های شرایط مرزی یا مقادیر اولیه، داده می شوند.
در تحلیل و بررسی الگوریتم ها، روابط بازگشتی اهمیت زیادی دارند. اگر یک الگوریتم به گونه ای ارائه شود که یک مساله را به زیر مساله های کوچک تری تبدیل شود، زمان اجرای آن را می توان با روابط بازگشتی توصیف کرد. به عنوان مثال، جست وجوی دودویی به این روش بررسی می شود. در ابتدا بررسی می نماییم که جز مورد نظر در میانه آرایه یا بردار وجود دارد یا خیر. اگر این عنصر در محل وسط بردار، وجود نداشته باشد، بررسی می نماییم که عنصر مورد نظر، از میانه بزرگ تر و یا کوچک تر می باشد. در این مرحله، نیمی از بردار حذف می شود و الگوریتم بر روی نیمه دیگر دوباره اجرا می شود. تعداد مقایسه ها در جست و جوی دودویی با رابطه زیر به دست می آید:
t(n)=t(n/2)+1
در واقع مرتبه اجرایی اصلی الگوریتم، از رابطه بالا به دست می آید. برای حل این رابطه با اصول حل روابط بازگشتی را بدانیم. در این مجموعه ابتدا رابطه های بازگشتی تدریس شده است. از جمله رابطه های بازگشتی بررسی شده می توان مواردی چون فاکتوریل، برج هانوی (Tower of Hanoi)، فیبوناچی (Fibonacci)، زاد و ولد خرگوش ها و … را نام برد.
روش های حل روابط بازگشتی که در این آموزش به صورت کامل ارائه شده است، حدس، تکرار، درخت بازگشت، قضیه اصلی، همگن و ناهمگن بودن، می باشد که به کمک مثال های مناسب آموزش داده شده اند. مبحث «رابطه های بازگشتی» در درس های «طراحی الگوریتم» و «ساختمان گسسته» مطرح می شود و در آزمون کارشناسی ارشد نیز از مباحث مهم این دروس بوده است.
توجه: مبحث زیر برنامه های بازگشتی را با این مبحث اشتباه نگیرید. زیر برنامه های بازگشتی در درس ساختمان داده ها در این لینک (+) بررسی شده است.
فهرست سرفصل ها و رئوس مطالب مطرح شده در این مجموعه آموزشی، در ادامه آمده است:
- درس یکم: روابط بازگشتی
- رابطه های بازگشتی
- روش حدس
- روش تکرار با جایگذاری
- رابطه های بازگشتی
- درس دوم: روش درخت بازگشت (Recursion Tree)
- درخت بازگشت برای روابط بازگشتی یک متغیره و دو متغیره
- درس سوم: قضیه اصلی – تغییر متغیر
- روش قضیه اصلی
- تغییر متغیر
- درس چهارم: رابطه های بازگشتی همگن
- رابطه های بازگشتی همگن
- رابطه های بازگشتی ناهمگن
- یک مورد خاص و متداول
- چند مساله معروف
این آموزش برای رشته های زیر مفید است:
- مهندسی کامپیوتر
- مهندسی فناوری اطلاعات یا IT
مشاهده آنلاین و یا دانلود رایگان این پیش نمایش، نیازمند 
مریوان :
خیلی ممنون بخاطر این آموزش. این تکمیل کننده آموزش طراحی الگوریتم است.
واقعا اموزش خیلی مفیدی برای کنکور ارشد ای تی و کامپیوتر به حساب میاد.
مهدی محمدی :
با سلام و عرض ادب
بسیار عالی و شیوا تدریس گردیده است، امیدوارم همیشه شاد و خوشبخت باشید. بهترین دو عالم را از خداوند بی همتا برای شما عزیزان خواستارم.
بهزاد :
خیلی عالی توضیح دادن این استاد. حتما درس های دیگه ای که اقای شیر افکن تدریس کردن رو تهیه میکنم. با اموزش ایشون من تو این درس ۲۰ شدم.
پیمان :
با سلام. پراکندگی بیش از حد در مباحث تدریس شده توسط فرادرس باعث سردرگمی میشه . لطفا مباحث مرتبط رو در یک مجموعه و تحت یک عنوان وسیع تر ارائه کنید تا علاوه بر صرفه جویی در وقت و هزینه ، باعث طبقه بندی در یادگیری شود.
ممنون
فرشید شیرافکن :
سلام-
در پاسخ به دوست عزیز پیمان.
مجموعه کامل تحت عنوان طراحی الگوریتم توسط اینجانب تهیه شده است.
فرشید شیرافکن