دانلود پاورپوینت توابع بازگشتی

بخشی از پاورپوینت

اسلاید 1 :

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

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

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

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

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

—

اسلاید 2 :

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

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

1- فاكتوريل

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

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

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

5- عمق درخت

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

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

اسلاید 3 :

پاسخ

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

1- فاكتوريل

                  شرط خاتمه                                                                          0! = 1

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

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

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

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

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

                             شرط خاتمه                                                               size = 0             

اسلاید 4 :

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

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

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

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

   عمق درخت

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

اسلاید 5 :

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

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

7-كپي درخت

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

اسلاید 6 :

تمارين

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

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

(به عنوان مثال عدد 2583 را به صورت 2583 چاپ كند)

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

(به عنوان مثال عدد 2583 را به صورت 3852 چاپ كند)

اسلاید 7 :

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

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

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

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

اسلاید 8 :

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

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

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

F  )int num (

  {  if )num = 0(

       Return 1;

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

   }

—

اسلاید 9 :

حل

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

اسلاید 10 :

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

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

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

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

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