موضوع مقاله: متغیر استقرایی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # متغیر استقرایی | مقدمه: متغیر استقرایی (در شاخه علوم رایانه) به متغیری گفته می‌شود که در هر گام از اجرای یک حلقه به میزان ثابتی افزایش یا کاهش می‌یابد و یا مقدار آن تابعی خطی از یک متغیر استقرایی دیگر در حلقه است. | ## بخش 1: متغیر استقرایی | به عنوان مثال، در کد زیر متغیرهای i و j متغیرهای استقرایی هستند؛ زیرا در هر گام از حلقه مقدار i یک واحد افزایش می‌یابد و j نیز با i رابطه خطی دارد:for (i = 0; i <10; ++i) { j = 17 * i; } کاربرد در روش کاهش قدرت یکی از روش‌های رایج در بهینه‌سازی‌های کامپایلر -کامپایلر بهینه‌ساز- کشف وجود متغیرهای استقرایی و جایگزینی دستورات مربوط به آن‌ها با دستورات حاوی محاسبات ساده‌تر است؛ برای مثال، با فرض این که عملیات مربوط به جمع یک متغیر با یک مقدار ثابت از عملیات ضرب آن در یک مقدار ثابت، ساده‌تر و سبک‌تر است، کد قسمت قبل را می‌توان به صورت زیر تغییر داد:j = -17; for (i = 0; i <10; ++i) { j = j + 17; //جایگزینی ضرب‌های مکرر روی متغیر استقرایی با عمل ساده‌تر جمع }که در اینجا بجای ضرب j در متغیر گام حلقه (که همان متغیر استقرایی است)، هربار j با مقدار ثابت 17 جمع می‌شود. کاربرد در روش کاهش فشار ثبات گاهی اوقات، می‌توان این بهینه‌سازی را به صورت معکوس اعمال کرد و با این کار یک متغیر استقرایی را کاملاً از کدهای برنامه حذف کرد. در واقع، از این ایده استفاده می‌شود که با جایگزین کردن یک متغیر استقرایی با تابعی خطی از متغیر استقرایی موجود دیگری، که عملیات آن تابع خطی سبک باشد، می توان از در نظر گرفته شدن ثبات مجزایی از cpu برای این متغیر جلوگیری کرد. جایگزینی متغیر استقرایی متغیری که درون یک حلقه به‌روزرسانی می‌شود، در واقع در هر گام از حلقه مقداری را به خود می‌گیرد که وابسته به مقدار متغیر حلقه در آن گام است. به عنوان مثال، متغیری را در نظر بگیرید که در ابتدا ۲- بوده و در هر گام از حلقه ۲ واحد زیاد می‌شود. می‌توان به جای به‌روزرسانی چنین متغیری در هر گام از حلقه، در هر گام آن را مستقیماً بر حسب متغیر حلقه نوشت. | ## بخش 2: متغیر استقرایی | به عنوان مثال تحلیل واسبتگی یکی از این آنالیزهاست که با استفاده از جایگزینی متغیر استقرایی ساده‌تر می‌شود. مثال قطعه کد زیر را در نظر بگیرید.int c, i; c = 10; for (i = 0; i <10; i++) { c = c + 5; // متغیر استقرایی در هر حلقه، ۵ واحد افزایش می‌یابد }در این قطعه کد، متغیر c یک متغیر استقرایی است و در حلقه به‌روزرسانی می‌شود. ولی می‌توانیم به جای این که در هر حلقه ۵ واحد به آن اضافه کنیم، ارتباطی مستقیم بین c و متغیر حلقه یعنی i پیدا کنیم. برای یافتن این ارتباط، دقت می‌کنیم که رابطه‌ی این دو در واقع رابطه‌ای خطی با شیب ۵ است. با توجه به مقدار اولیه‌ی c یعنی ۱۰، می‌توانیم به سادگی مقدار عرض از مبدأ این رابطه‌ی خطی را نیز بیابیم که در واقع ۱۵ است. لذا می‌توانیم قطعه کد را به صورت زیر تغییر دهیم.int c, i; c = 10; for (i = 0; i <10; i++) { c = 5 * i + 15; // مقدار متغیر استقرایی، مستقیماً از روی مقدار متغیر حلقه محاسبه می‌شود }کاری که کردیم در واقع نمونه‌ای از جایگزینی متغیر استقرایی بود. | ## بخش 3: متغیر استقرایی | متغیرهای استقرایی غیرخطی در تمام مثال‌هایی که در بخش‌های قبل دیدیم، رابطه‌ای خطی بین متغیر استقرایی و متغیر حلقه وجود داشت. مثال ۱ قطعه کد زیر را در نظر بگیرید.int c, i; c = 0; for (i = 0; i <10; i++) { c = c + i; // مقدار متغیر استقرایی، هر بار به اندازه‌ی متغیر حلقه اضافه می‌شود }در این مثال، مقدار متغیر استقرایی هر در گام از حلقه، به اندازه‌ی مقدار متغیر حلقه افزایش می‌یابد. هیچ‌گونه رابطه‌ی خطی‌ای بین c و i وجود ندارد اما با کمی دقت درمی‌یابیم که در هر گام از حلقه، مقدار c در واقع جمع اعداد ۰ تا i است. پس به نظر می‌رسد که می‌توان جایگزینی متغیر استقرایی را با استفاده از یک رابطه‌ی چندجمله‌ای انجام داد. قطعه کد تغییر یافته به صورت زیر خواهد بود:int c, i; c = 0; for (i = 0; i <10; i++) { c = i * (i + 1) / 2; // مقدار متغیر استقرایی، مستقیماً از روی مقدار متغیر حلقه محاسبه می‌شود } مثال ۲ قطعه کد زیر را در نظر بگیرید.int j, i; j = 1; for (i = 0; i <10; i++) { j = j <<1; // متغیر استقرایی در هر گام از حلقه یک بار شیفت چپ می‌خورد }در این مثال، مقدار متغیر استقرایی در هر گام از حلقه، یک شیفت به چپ می‌خورد. | ## جمع‌بندی | باز هم رابطه‌ی خطی‌ای بین j و i مشاهده نمی‌شود اما به سادگی می‌توان دریافت که در هر گام از حلقه، مقدار j در واقع برابر با i + 1 بار شیفت به چپ خورده‌ی عدد ۱ است.