لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت توابع بازگشتي توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت توابع بازگشتي قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

          اگر بتوان مسئله ای را با حلقه هاي تكرار پياده سازي كرد ، ترجيحا از حلقه هاي تكرار استفاده می كنيم ، زیرا توابع بازگشتي نسبت به حلقه های تکرار به حافظه ی بیشتری نیاز دارند . اما از نظر زماني هيچ تفاوتی در استفاده از حلقه هاي تكرار و توابع بازگشتي نيست به شرط آنكه روش حل يكي باشد و تنها پياده سازي متفاوت باشد.

v به عنوان مثال موضوعيّت درخت يك تعريف بازگشتي است.

   طرح تابع بازگشتي مستلزم داشتن تفكر بازگشتي است ؛

       به عبارت ديگر :

      باید بتوان يك مساله را با مساله اي دقيقاً از همان نوع و جنس ، امّا با تعداد داده هاي كمتر پاسخ داد .

—

اسلاید ۲ :

طرح تابع بازگشتي مستلزم داشتن تفكر بازگشتي است .اين نوع تفكر مستلزم دو نكته است:
۱- داشتن منطق بازگشتي
۲- شرط خاتمه(خروج)

مثال : براي موارد زير منطق بازگشتي و شرط خاتمه رابنويسيد.

۱- فاكتوريل

 ۲- عدد n ام فيبوناچي

 ۳- جمع عناصر يك آرايه

 ۴- معكوس كردن يك آرايه

۵- عمق درخت

 ۶- تعداد node درخت

 ۷- كپي كردن درخت

اسلاید ۳ :

پاسخ

                  منطق بازگشتي :   n! = n Í (n-1)!                                                

۱- فاكتوريل

                  شرط خاتمه                                                                          ۰! = ۱

                        منطق بازگشتي :                       عدد(n-2) + عدد (n-1) = عدد nام  

۲- عدد n ام فيبوناچي

                              شرط خاتمه                                                     n=1 → ۱ يا n=2

                              منطق بازگشتي :  باقي مانده آرايه اوّليه+عددآخر آرايه= جمع عناصرآرايه

۳- جمع عناصريك آرايه                              

                             شرط خاتمه                                                               size = 0             

اسلاید ۴ :

                                                          منطق بازگشتي: معكوس كردن آرايه باقي مانده+جابجایی عنصر اول و آخر
۴- معكوس كردن

           يك آرايه
                           
                          شرط خاتمه   size = 0                                       يا  size =1

۵- درخت : مي دانيم كه درخت يا تهي (شرط خاتمه)است و يا شامل يك عنصر به نام ريشه و دو زير درخت چپ و راست(منطق بازگشتي).

                       منطق بازگشتي:                (زيردرخت راست + زيردرخت چپ)max  + ۱

   عمق درخت

                       شرط خاتمه                               ريشه وجود نداشته باشد(درخت تهي)

اسلاید ۵ :

                      منطق بازگشتي: (تعداد nodeزيردرخت راست+تعداد nodeزيردرخت چپ)É۱
۶- nodeدرخت      
                        شرط خاتمه                                   ريشه وجود نداشته باشد(درخت تهي)

                     منطق بازگشتي :       كپي كردن زير درخت چپ و كپي كردن زير درخت راست

۷-كپي درخت

                     شرط خاتمه                                      ريشه وجود نداشته باشد(درخت تهي) 

اسلاید ۶ :

تمارين

۱- كدهاي توابع مثال بالا را به زبان C بنويسيد.

۲- تابع بازگشتي بنويسيد كه ارقام يك عدد صحيح را به ترتيب ارزش مكاني چاپ نمايد.

(به عنوان مثال عدد ۲۵۸۳ را به صورت ۲۵۸۳ چاپ كند)

۳- تابع بازگشتي بنويسيد كه ارقام يك عدد صحيح را به ترتيب عكس ارزش مكاني چاپ نمايد.

(به عنوان مثال عدد ۲۵۸۳ را به صورت ۳۸۵۲ چاپ كند)

اسلاید ۷ :

تحليل زماني توابع بازگشتي

شامل دو فاز است :

                 فازاوّل :   بدست آوردن يك معادله ي بازگشتي ازروي الگوريتم بازگشتي .

                 فاز دوّم :  حل رياضي معادله ی بازگشتي و ارائه پاسخ صريح .

اسلاید ۸ :

فازاوّلبدست آوردن يك معادله ي بازگشتي ازروي الگوريتم بازگشتي

üبرای به دست آوردن معادله رياضی مورد نظر ابتدا بايد حالت بازگشتی تابع و شرط پايان آن را بررسی کنيم.

مثال : رابطه ی رياضی تابع بازگشتی زیر را به دست آوريد.

F  )int num (

  {  if )num = 0(

       Return 1;

      Return ) num + F ) num -1 ( ( ;

   }

—

اسلاید ۹ :

حل

اگر زمان مورد نياز برای محاسبه تابع f با سايز ورودی num را (n) Tفرض کنيم رابطه رياضی بازگشتی برنامه به شکل  +۲(n- 1) = T(n)T با شرط  پايان = ۰ (۰)T  خواهد بود.عدد ۲به ازای دو عمل اجرايی مقايسه در if و جمع پايانی اضافه می شود .

اسلاید ۱۰ :

فاز دوّم : حل رياضي معادله بازگشتي

سه روش اصلی برای حل يک رابطه رياضی وجود دارد:

 ۱- تکرار با جايگذاری

 ۲- حل معادله مشخصه

 ۳- قضيه اصلی (master method)