نحوه حل الگوریتم های بازگشتی با استفاده از رسم درخت بازگشتی؟

[sajad_3dmax]

با عرض سلام. از درخت های بازگشتی برای حل چه روابط بازگشتیی استفاده میشود؟نحوه رسم اون رو هم لطفا توضیح بدبد.باتشکر فراوان
سیدسجاد

[xxxxx_xxxxx]

سلام،
درخت بازگشتی رو برای توابع بازگشتی ایی رسم میکنیم که استراتژی تقسیم و حل (Divide and Conquer) رو به کار گرفتند.

یعنی از کل به جزء حرکت میکنند. و وقتی به جزء رسیدند، مسئله جزء رو حل میکنند و بر میگردند به سمت کل.
برای رسم درخت هم، "کل" ریشه درخت هست و "جزء"، برگ های درخت هست.

برای مثال، الگوریتم بازگشتی سری فیبوناچی رو میتونید براش درخت بازگشتی رسم کنید. که هر گره، دو فرزند داره. چون توی فرمول بازگشتی فیبوناچی داریم:


fib(n) = fib(n-1) + fib(n-2)
fib(n) ریشه درخت هست. و fib(n-1) و fib(n-2) بچه های این ریشه هستند. به همین ترتیب، بچه های fib(n-1) برابر هستند با fib(n-2) و fib(n-3). همینطور تا آخر ادامه میدیم تا برسیم به شرط های پایانی الگوریتم که اگر n=1 یا n=0 شد، آنوقت دیگه ادامه نمیدیم و جوا اون گره میشه 1. حالا به سمت بالا بر میگردیم و جواب ها رو با هم ترکیب میکنیم تا در نهایت به ریشه برسیم.

موفق باشید/

[sajad_3dmax]

ممنونم که جواب سوالمو دادین.اما من مثال های مشکل رو میخوام حل کنم.برای رسم درخت بازگشتی تابع tn=tn/3+t2n/3+On (حل این تابع تو کتاب clrs هست) مقدار cn تو ریشه درخت قرار داده شده(که در واقع هزینه ترکیب جواب های جزئی تقسیم و حل این تابع هستش).لطف کنین اگه میشه این تالع رو تحلیل کنید.ممنون .بعد از حل این مشکل یه سوال کوچیک هم دارم که ان شا الله بعدا میپرسم