خوش آموز درخت تو گر بار دانش بگیرد، به زیر آوری چرخ نیلوفری را


تعریف توابع به صورت بازگشتی

تعریف توابع به صورت بازگشتی
نویسنده : امیر انصاری
یک روش جایگزین برای توصیف جملات یک دنباله، به جای اینکه یک قاعدۀ کلی برای آن دنباله تعریف کنیم، اینست که دنباله را به صورت بازگشتی (recursively) تعریف کنیم. برای انجام این کار، جملۀ اول، یا چند تا از جملات آغازین، را تعیین می کنید و چگونگی یافتن سایر جملات را با استفاده از جملاتی که قبل از آنها می آیند، توصیف می کنید.

سیستم یکپارچۀ سازمانی راهکار



قوانین جبر: قاعدۀ بازگشتی برای دنباله های حسابی برابر با \(a_n=a_{n-1}+d\) ، و قاعدۀ بازگشتی برای دنباله های هندسی برابر با \(g_n=rg_{n-1}\) می باشد.

در اینجا مثالی از یک دنبالۀ تعریف شده به صورت بازگشتی داریم. این مقادیر را فرض بگیرید: \(a_1=6\) و \(a_n=2a_{n-1}+3\) . این فرمول به شما می گوید، برای یافتن یک جمله در این دنباله، به جملۀ قبلی آن نگاه می کنید \((a_{n-1})\) ، آن را دوبرابر می کنید \((2a_{n-1})\) ، و \(3\) را به آن می افزایید. اولین جمله \(6\) می باشد، بنابراین دومین جمله برابر است با \(3\) بعلاوۀ دوبرابرِ \(6\)، که \(15\) می شود. جملۀ سوم برابر است با \(3\) بعلاوۀ دوبرابرِ \(15\)، که \(33\) می شود. در اینجا چند تا دیگر از جملات این دنباله را آورده ایم: \(\{6, 15, 33, 69, 141, ...\}\)

نکات فنی: گاهی اوقات، شما باید اعداد موجود در یک دنبالۀ بازگشتی را از روی قاعده ای که به شما داده می شود، لیست کنید، و اگر واقعاً خوش شانس باشید، شما می توانید خودتان قاعده ای را بسازید. البته در این کتاب قصد آموزش چگونگی ایجاد قاعده برای دنباله های بازگشتی را نداریم، اگر وارد مباحث ریاضیات گسسته (discrete mathematics) شوید، می توانید این کار را انجام بدهید!

شما می توانید دنباله ها را به صورت بازگشتی با ارجاع دادن به بیش از یکی از جملات قبلی تعریف کنید. به عنوان مثال، فرض کنید \(a_n=3a_{n-2}+a_{n-1}\) . این قاعده به شما می گوید برای یافتن جملۀ \(n\)ام در این دنباله، شما باید به دو جملۀ قبل از آن نگاه کنید، جمله ای را که در دو موقعیت قبل تر قرار دارد در \(3\) ضرب کنید، یعنی \(3(a_{n-2})\) ، و سپس حاصل آن را به جملۀ قبلی یعنی \(a_{n-1}\) اضافه کنید.

برای آغاز نوشتن جملات این دنباله، شما نیاز دارید تا دو جملۀ متوالی را شناسایی کنید. در این دنبالۀ خاص، شما تصمیم می گیرید تا \(b_1=4\) و \(b_2=-1\) باشد. در اینجا چگونگی ادامه یافتن این جملات را می بینید (توجه: اگر شما بدنبال ششمین جمله هستید، نیاز دارید تا جملۀ \([n-1]\) که پنجمین جمله می شود، و جملۀ \([n-2]\) که چهارمین جمله می شود، را داشته باشید):
$$
b_1=4, b_2=-1 \\[2ex]
b_n=3b_{n-2}+b_{n-1} \\[2ex]
b_3=3b_1+b_2=3(4)+(-1)=12-1=11 \\[2ex]
b_4=3b_2+b_3=3(-1)+11=-3+11=8 \\[2ex]
b_5=3b_3+b_4=3(11)+8=33+8=41 \\[2ex]
b_6=3b_4+b_5=3(8)+41=24+41=65
$$
دنباله هایی که به صورت بازگشتی شکل گرفته اند، از جملات پیشین در دنباله ها استفاده می کنند تا جملات بعدی را شکل دهند. قواعدی که برای نوشتن این دنباله ها استفاده می شود به سودمندیِ قواعدی که به شما امکان می دهند تا جملات \(50\)ام یا \(100\)ام را بدون دانستن جملات قبلیشان بیابید (مانند دنباله های حسابی و هندسی)، نمی باشند. اما گاهی اوقات نوشتن قاعدۀ بازگشتی ساده تر است.

به عنوان مثال، اگر شما بدانید که حقوق امسال شما در شغل جدیدتان \($20,000\) و در سال بعد \($25,000\) ، و در سالهای بعد از آن در هر سال به میزان \(80\) درصد از حقوق دو سال قبلش بعلاوۀ \(40\) درصد از حقوق سال قبلش باشد، آیا تمایل خواهید داشت که قرارداد کاری جدیدتان را امضاء کنید؟ این قانون اینگونه تعبیر می شود: \(b_n=0.8b_{n-2}+0.4b_{n-1}\) . با استفاده از دو جملۀ اول و این قانون، حقوق شما برای \(5\) سال اول به این شکل خواهد بود:
$$ \{20,000, 25,000, 26,000, 30,400, 32,960, ...\} $$



نمایش دیدگاه ها (0 دیدگاه)

دیدگاه خود را ثبت کنید:

انتخاب تصویر ویرایش حذف
توجه! حداکثر حجم مجاز برای تصویر 500 کیلوبایت می باشد.