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