فاکتوریل غیربازگشتی

این تابع به صورت زیر تعریف می‌شود.

اگر تابع را بررسی کنیم، متوجه می‌شویم که پس از هر مرحله برای m دو حالت اتفاق می‌افتد:

1ـ مقدارش کم می‌شود.

2ـ مقدار m تا زمانی ثابت می‌ماند که مقدار n آنقدر کاهش بیابد تا به صفر برسد و از آن پس مقدار m کم می‌شود.

پس مطمئن هستیم که m بالاخره بعد از چند مرحله کاهش می‌یابد تا به صفر برسد و سپس مقدار n یک واحد افزایش پیدا می‌کند. وقتی m به صفر برسد، تابع آکرمن به جواب رسیده است. اما نکته‌ این است که به ازای تمامی مقادیر ورودی m میزان رشد n یکسان نیست و برای بعضی از مقادیر m میزان رشد n بشدت زیاد خواهد بود. مثلا برای مقدار 3 ورودی برای m در مرحله nام خروجی تابع برابر 3- (³⁺ⁿ)2 می‌شود. برای مقادیر کوچک‌تر از 3خروجی، تابع از این مقدار نیز کمتر می‌شود اما برای مقادیر بزرگ‌تر مساوی با 4 خروجی، تابع بسیار بزرگ می‌شود. مثلا برای ورودی m برابر 4 و n برابر 4 مقدار تابع عددی برابر 3ـ2265533 می‌شود که عددی بسیار بزرگ است. همان طور که مشخص است به ازای مقادیر بزرگ‌تر مساوی 4 ، رشد n بسیار زیاد است و نمی‌توان آن را حساب کرد.

اگر تابع آکرمن را به صورت (Ackerman (n,n تعریف کنیم به یک تابع تک‌متغیر تبدیل می‌شود که رشد مقادیر آن بسیار زیاد است و نسبت به توابع دیگر تک‌متغیر دارای رشد سریع‌تری است.

این تابع به صورت زیر تعریف می‌شود:

که نسبت به خود تابع آکرمن رشد سریع تری دارد.

حال چگونه برنامه‌ای بنویسیم که تابع آکرمن را به ازای 2 مقدار ورودی حساب بکند؟ برای حساب کردن این تابع در اینجا از 3 روش استفاده و سرانجام آنها را با هم مقایسه می‌کنیم.

روش اول به صورت بازگشتی است. یعنی آنقدر تابع را فراخوانی می‌کنیم که مقدار n به صفر برسد. کد این روش به صورت زیر است:

unsigned int naive_ackermann(unsigned int m, unsigned int n) {

calls++;

if (m == 0)

return n + 1;

else if (n == 0)

return naive_ackermann(m - 1, 1);

else

return naive_ackermann(m - 1, naive_ackermann(m, n - 1));

}

این تابع ابتدا بررسی می‌کند که اگر m برابر صفر بود، مقدار n+1 را به خروجی برمی‌گرداند. در غیر این صورت آنقدر به صورت بازگشتی اجرا می‌شود تا مقدار n به صفر برسد و اگر برابر صفر شد، تابع خودش را ورودی m -1 و 1 فراخوانی می‌کند.

روش دوم به صورت تکراری است. یعنی برای محاسبه مقدار تابع از یک حلقه استفاده می‌کنیم. این روش تقریبا شبیه روش قبلی است. کد این روش به صورت زیر است:

unsigned int iterative_ackermann (unsigned int m, unsigned int n) {

calls++;

while (m != 0) {

if (n == 0) {

n = 1; }

else {

n = iterative_ackermann(m, n-1);}

m--;

}

return n + 1;

}

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

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

unsigned int formula_ackermann(unsigned int m, unsigned int n) {

calls++;

while(1) {

switch(m) {

case 0: return n + 1;

case 1: return n + 2;

case 2: return (n «« 1) + 3;

case 3: return (1 «« (n+3)) - 3;

default:

if (n == 0) {

n = 1; }

else {

n = formula_ackermann(m, n - 1); }

m--;

break; }

}

}

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

نتیجه از این قرار است:

Naive: 65533 (2862984010 calls)

Iterative: 65533 (1431459240 calls)

Formula: 65533 (2 calls)

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

امیربهاالدین سبط الشیخ