آموزش زبان کاتلین – درس ۱۲ (تابع بازگشتی)

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

طرز کار تکنیک Recursion در دنیای برنامه‌نویسی

fun main(args: Array<String>) {
... .. ...
recurse()
... .. ...
}

fun recurse() {
... .. ...
recurse()
... .. ...
}

تابع بازگشتی در اینجا از داخل خودِ تابع ()recurse فراخوانی می‌شود. طرز کارش را در تصویر زیر مشاهده کنید:

همانطور که می‌بینید ساختار بالا یک حلقۀ اجرای همیشگی است که به صورت تودرتو تابع ()recurse را فرخوانی می‌کند ولی هیچگاه به پایان نمی‌رسد. (این کار تا زمانی که حافظه گنجایش نداشته باشد ادامه خواهد داشت). برای جلوگیری از فرخوانی بی‌نهایت از if…else یا رویکردهای دیگر استفاده می‌شود.

مثال: پیدا کردن فاکتوریل یک عدد به کمک تابع بازگشتی در کاتلین

فاکتوریل هر عدد طبیعی در ریاضیات از حاصل‌ضرب آن عدد در تمام اعداد طبیعی کوچکتر از آن بدون صفر به دست می‌آید و با !n نشان داده می‎‌شود. با این حساب فاکتوریل ۳ برابر است با ۱*۲*۳ که می‌شود ۶٫ فاکتوریل ۴ برابر است با ۱*۲*۳*۴ یعنی ۲۴٫ فاکتوریل ۲ برابر ۲، ۱ برابر ۱ و طبق قاعده فاکتوریل ۰ برابر ۱ است. حالا می‌خواهیم همین کار را با یک کد ساده در کاتلین انجام دهیم. این مسئله را به سادگی می‌توان با یک تابع بازگشتی انجام داد:

fun main(args: Array<String>) {
val number = 4
val result: Long

result = factorial(number)
println("Factorial of $number = $result")
}

fun factorial(n: Int): Long {
return if (n == 1) n.toLong() else n*factorial(n-1)
}

خروجی:

Factorial of 4 = 24

طرز کار برنامه:

در تصویر پایین مراحل مختلف فرخوانی تابع factorial برای عدد ۴ را می‌توانید مشاهده کنید:

factorial(4) // 1st function call. Argument: 4
۴*factorial(3) // 2nd function call. Argument: 3
۴*(۳*factorial(2)) // 3rd function call. Argument: 2
۴*(۳*(۲*factorial(1))) // 4th function call. Argument: 1
۴*(۳*(۲*۱))
۲۴

تکنیک Tail Recursion در کاتلین

Tail Recursion مفهوم جدیدی است که در برخی زبان‌ها همچون کاتلین وجود دارد. تعدادی از زبان‌های برنامه‌نویسی برای بهینه‌سازی فرخوانی‌ها توابع بازگشتی از این تکنیک استفاده می‌کنند با این حال زبان‌هایی همچون پایتون از آن پشتیبانی نمی‌کنند.

در تکنیک بازگشتی رایج، ابتدا تمامی فرخوانی‌ها انجام می‎شود و خوب که به انتها رسیدیم دریافت مقادیر آغاز می‌شود. مثلاً در تصویر بالا از فاکتوریل ۴ به فاکتوریل ۳ آمدیم سپس فاکتوریل ۲ و در انتها یک. خب حالا که به آخر رسیدیم مقدار فاکتوریل ۱ که ۱ است برگردانده می‌شود و فاکتوریل ۲ از آن استفاده کرده سپس مقدار فاکتوریل ۲ به بالا بازگشت داده می‌شود. این تکنیک شاید برای مقادیر کوچک پاسخگو باشد ولی وقتی تعداد فرخوانی‌ها افزایش پیدا می‌کند مشکل‌ساز خواهد شد.

در تکنیک Tail Recursion ابتدا محاسبات بهینه می‌شود، سپس فرخوانی‌ها صورت می‌گیرد. این کار باعث می‌شود تا تابع بازگشتی همچون یک حلقۀ ساده عمل کند و بروز خطای سرریزِ حافظه به حداقل برسد.

شرایط استفاده از Tail Recursion

این تکنیک تنها روی آن دسته از توبع بازگشتی اثر دارد که در فرخوانی آخر هیچ کار اضافه‌ای روی تابع انجام نگیرد. مثلا تابع فاکتوریل چنین شرایطی ندارد چون در آخرین مرحله (n*factorial(n-1 را داریم. که علاوه بر فراخونی تابع بازگشتی در عدد n نیز ضرب شده است.

fun factorial(n: Int): Long {

if (n == 1) {
return n.toLong()
} else {
return n*factorial(n - 1)
}
}

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

fun fibonacci(n: Int, a: Long, b: Long): Long {
return if (n == 0) b else fibonacci(n-1, a+b, a)
}

در کاتلین تکنیک Tail Recursion را می‌توان روی توابع بازگشتیِ مجاز با استفاده از مودیفایر tailrec اجرا کرد.

مثال:

import java.math.BigInteger

fun main(args: Array<String>) {
val n = 100
val first = BigInteger("0")
val second = BigInteger("1")

println(fibonacci(n, first, second))
}

tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
return if (n == 0) a else fibonacci(n-1, b, a+b)
}

خروجی:

۳۵۴۲۲۴۸۴۸۱۷۹۲۶۱۹۱۵۰۷۵

این برنامه صدمین عدد در سری فیبوناچی را محاسبه و نمایش می‌دهد. از آنجایی که خروجی می‌تواند عدد بزرگی باشد از کلاس BigInteger متعلق به کتابخانه‌ی جاوا استفاده شده است. دقت کنید قبل از تابع fibonacci از مودیفایر tailrec استفاده شده که به معنی مجاز بودن کامپایلر در استفاده از تکنیک Tail Recursion روی این تابع است. کامپایلر با دیدن این مودیفایر، بهینه‌سازی لازم را انجام خواد داد.

اگر تابع بالا را بدون استفاده از این تکنیک برای به دست آوردن ۲۰ هزارمین عدد سری فیبوناچی به کار برید با خطای سرریز (java.lang.StackOverflowError) مواجه می‌شوید. ولی با استفاده از این تکنیک چنین خطایی رخ نمی‌دهد. دلیلش بهینه بودن کد و استفاده از حلقه‌های معمول برای محاسبات و نه فرخوانی تودرتو تابع بازگشتی به شیوۀ سابق است.

استفاده از تکنیک Tail Recursion برای فاکتوریل

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

fun main(args: Array<String>) {
val number = 5
println("Factorial of $number = ${factorial(number)}")
}

tailrec fun factorial(n: Int, run: Int = 1): Long {
return if (n == 1) run.toLong() else factorial(n-1, run*n)
}

خروجی:

Factorial of 5 = 120

کامپایلر اکنون با دیدن مودیفایر tailrec به راحتی می‌تواند تابع را بهینه‌سازی کرده و با خطای سرریز مقابله کند.