مفاهیم بازگشت در برنامه‌نویسی C : از فاکتوریل تا مدیریت پشته - قسمت هفدهم آموزش برنامه نویسی C

در قسمت قبل آموزش برنامه نویسی C به آشنایی با متغیرهای محلی و رویه‌ها در زبان C پرداختیم. در این قسمت به مفاهیم بازگشت در برنامه‌نویسی C می پردازیم.

تا الان با فراخوانی‌های ساده سروکار داشتیم، به این صورت که به هر تابع یک اسم منحصر به فرد اختصاص داده می‌شد و فراخوانی آن نیز به سادگی انجام می‌گرفت. حالا می‌خواهیم روی بازگشت (Recursion) تمرکز کنیم، جایی که یک تابع خودش را فراخوانی می‌کند. بازگشت می‌تواند ابزار قدرتمندی باشد، اما اگر قوانین آن را درک نکنید، استفاده از آن دشوار خواهد بود.

یکی از مسائل کلاسیک در مبحث بازگشت، محاسبه فاکتوریل است. تابع فاکتوریل به‌صورت زیر تعریف می‌شود:

f(n) = 1 زمانی که n برابر 1 باشد در غیر این صورت، f(n) = n × f(n – 1)

برنامه‌نویسی این تعریف به‌صورت کد C در کد 17-1 آمده است.

کد 17-1: برنامه‌ای برای محاسبه فاکتوریل

ابتدا factor(5) را برای به‌دست‌آوردن فاکتوریل 5 فراخوانی می‌کنیم. برای این کار، به factor(4) نیاز داریم، بنابراین فراخوانی factor(5) را معلق نگه می‌داریم تا factor(4) را صدا بزنیم. اما factor(4) به factor(3) نیاز دارد، پس باز هم کار را معلق نگه می‌داریم و factor(3) را فراخوانی می‌کنیم. حالا factor(3) به factor(2) و factor(2) به factor(1) نیاز دارد.

در نهایت، factor(1) به چیز دیگری احتیاج ندارد، بنابراین 1 را به فراخواننده‌اش، یعنی factor(2)، برمی‌گرداند. تابع factor(2) در حال اجرا است، پس2×1 را محاسبه کرده و 2 را به فراخواننده‌اش، factor(3)، برمی‌گرداند. سپس، factor(3) مقدار برگشتی (2) را گرفته، 2×3 را محاسبه کرده و 6 را به فراخواننده‌اش، factor(4)، برمی‌گرداند. به انتها نزدیک می‌شویم، factor(4) مقدار 6 × 4 را محاسبه کرده و 24 را برمی‌گرداند. در نهایت، factor(5) مقدار 24 × 5 را محاسبه کرده و 120 را برمی‌گرداند.

هنگامی که این برنامه را در دیباگر اجرا می‌کنید، باید ببینید که با محاسبه فاکتوریل، مقدار پشته (Stack) افزایش و کاهش پیدا می‌کند همچنین یک پشته با پنج فریم برای تابع factor که برای هر فراخوانی، یک فریم اختصاص‌داده‌شده است: factor(1)، factor(2)، factor(3)، factor(4) و factor(5).

دو قانون برای استفاده از بازگشت وجود دارد:

• هر فراخوانی به تابع باید مسئله را ساده‌تر کند.
• باید یک نقطه پایان وجود داشته باشد.

بیایید ببینیم این قوانین چگونه در برنامه فاکتوریل ما عمل می‌کنند. برای محاسبه factor(5)، نیاز به محاسبه factor(4) داریم. اولین قانون رعایت می‌شود زیرا factor(4) ساده‌تر از factor(5) است. دیریازود، به factor(1) می‌رسیم که همان نقطه پایان است و این موضوع، قانون دوم را برآورده می‌کند.

بیایید قوانین را نقض کنیم تا ببینیم چه اتفاقی می‌افتد. برنامه را تغییر می‌دهیم و سعی می‌کنیم factor(-1) را محاسبه کنیم.

آیا این کار دو قانون را برآورده می‌کند؟ خب، factor(-1) به factor(-2) نیاز دارد که به factor(-3) نیاز دارد و به همین ترتیب تا اینکه به 1 برسیم. اما هیچ راهی برای رفتن از -1 به 1 با تفریق وجود ندارد، بنابراین هیچ راهی برای پایان دادن به برنامه نداریم.

اجراکردن این برنامه روی سیستم لینوکس من خروجی زیر را نمایش می‌دهد:

سیستم با کمبود حافظه‌ی پشته مواجه شد و برنامه به دلیل نقض محدودیت‌های حفاظت حافظه پردازنده x86 متوقف شد. روی سیستم‌های دیگر، نتایج ممکن است متفاوت باشد. برای مثال، روی پردازنده‌های ARM، پشته ممکن است با heap تداخل پیدا کند و آن را خراب کند (درباره heap در فصل‌های بعد بیشتر توضیح داده می‌شود)، یا چیز دیگری از بین برود. درهرصورت، تمام‌شدن حافظه‌ی پشته، اتفاق خوبی نیست.

سبک برنامه‌نویسی

در این دوره آموزشی، تا جای ممکن سعی می‌کنیم از سبک برنامه‌نویسی خوب استفاده کنیم. برای مثال، اطمینان حاصل کرده‌ایم که در ابتدای هر تابع یک بلوک کامنت قرار دهیم و همیشه بعد از هر اعلام متغیر، یک کامنت اضافه کنیم. سبک برنامه‌نویسی خوب به دو دلیل به این شکل طراحی شده است: برای اینکه به برنامه‌نویسی که بعد از شما می‌آید، ایده‌ی واضحی از کاری که انجام داده‌اید بدهد و خطاکردن را دشوار کند.

ما در مثال فاکتوریل، یکی از این قوانین را نقض کردیم:

مشکل آن چیست؟ نوع داده‌ی int علامت‌دار است، اما شما فقط می‌توانید فاکتوریل را روی اعداد مثبت محاسبه کنید. می‌توانستیم تابع خود را به شکل زیر بنویسیم:

نوشتن آن به این شکل، ارسال یک عدد منفی را غیرممکن می‌کند. توجه داشته باشید که کامپایلر با کمال لطف، عدد ۱- را به یک عدد بدون علامت (۴۲۹۴۹۶۷۲۹۵) بدون هیچ هشداری تغییر می‌دهد، مگر اینکه از کلید کامپایلر -Wconversion  استفاده کنید. GCC صدها گزینه دارد و اینکه بفهمیم از کدام یک استفاده کنیم، هنر خاص خود را می‌طلبد.

بااین‌حال، نسخه‌ی اول آن خط کد، دو مزیت داشت؛ مثال خوبی از سبک بد است و به ما اجازه داد تا سرریز پشته را با factor(-1) نشان دهیم.

خلاصه

همان‌طور که متوجه شده‌اید، این دوره به فصل‌های جداگانه تقسیم شده است. چرا؟ بدیهی است که خواندن آن را آسان‌تر کند. هر فصل واحد قابل درکی از اطلاعات را به خواننده ارائه می‌دهد.

برنامه‌های کامپیوتری نیز نیاز به تقسیم‌شدن به قطعات کوچک دارند. پیگیری یک برنامه‌ی ۷۵۰،۰۰۰ خطی غیرممکن است. درحالی‌که درک کامل یک رویه‌ی ۳۰۰ خطی امکان‌پذیر است. متغیرهای محلی نیز به سازمان‌دهی برنامه کمک می‌کنند. اگر متغیری دارید که در یک‌رویه‌ی ۳۰۰ خطی محلی است، می‌دانید که فقط در همان ۳۰۰ خط استفاده می‌شود. از طرف دیگر، یک متغیر سراسری را می‌توان در هر جایی از یک برنامه‌ی ۷۵۰،۰۰۰ خطی استفاده کرد.

کلید نوشتن کد خوب، قابل‌فهم و ساده‌کردن آن است. رویه‌ها به شما کمک می‌کنند تا برنامه خود را به واحدهای ساده و قابل‌فهم تقسیم کنید که این امر به نوشتن کدهایی با قابلیت اطمینان بیشتر و نگهداری آسان‌تر کمک می‌کند.