توابع بازگشتی در برنامه نویسی کاتلین

توابع بازگشتی در برنامه نویسی کاتلین

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

عملکردی که خود را فراخوانی می کند به عنوان تابع بازگشتی شناخته می شود. و این روش به عنوان بازگشت شناخته می شود.

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

بازگشت در برنامه نویسی کاتلین چگونه کار می کند؟

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

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

در اینجا، تابع ()recurse  از خود تابع ()recurse  فراخوانی می شود. نحوه کار این برنامه به صورت زیر است:

در مثال فوق، فراخوان بازگشتی برای همیشه ادامه دارد و باعث بازگشت بی نهایت می شود.

برای جلوگیری از بازگشت نامحدود از گزاره های  if…else  (یا رویکرد مشابه) در جایی که یک شاخه فراخوان بازگشتی را برقرار می کند و دیگری نمی تواند استفاده شود.

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

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 
۴*(۳*(۲*۱))                 
۲۴

بازگشت انتهایی در برنامه نویسی کاتلین

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

بازگشت انتهایی در برنامه نویسی کاتلین چیست؟

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

در بازگشت انتهایی، ابتدا محاسبات انجام می شود، سپس فراخوان های بازگشتی اجرا می شوند (فراخوان بازگشتی نتیجه مرحله فعلی شما را به فراخوان بازگشتی بعدی منتقل می کند). این باعث می شود فراخوان برگشتی معادل حلقه باشد و از خطر سرریز پشته یا همان (stack overflow) جلوگیری شود.

شرایط بازگشت انتهایی در برنامه نویسی کاتلین

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

مثال ۱: واجد شرایط بازگشت انتهایی نیست زیرا فراخوانی تابع به خود n*factorial(n-1)  آخرین عملیات نیست.

fun factorial(n: Int): Long {

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

مثال ۲: واجد شرایط بازگشت انتهایی است زیرا فراخوانی تابع به خود (n-1 ، a + b ، a) آخرین عملیات است.

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

برای اینکه به کامپایلر در برنامه نویسی کاتلین بگویید که بازگشت را به صورت بازگشت انتهایی انجام دهد، باید تابع را با tailrec modifier علامت گذاری کنید.

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

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 modifier مشخص شده و عملکرد برای فراخوان برگشتی انتهایی واجد شرایط است. از این رو، کامپایلر بازگشت را در این حالت بهینه می کند.

اگر سعی کنید ۲۰۰۰۰مین عذذ(یا هر عدد صحیح بزرگ دیگر) از سری فیبوناچی را بدون استفاده از بازگشت انتهایی پیدا کنید ، کامپایلر java.lang.StackOverflowError را به صورت یک استثنا ایجاد می کند. با این حال، برنامه ما در بالا بسیار خوب کار می کند. به این دلیل است که ما از بازگشت انتهایی استفاده کرده ایم که از نسخه مبتنی بر حلقه بهینه شده به جای بازگشت سنتی استفاده می کند.

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

مثالی که برای محاسبه فاکتوریل عدد در مثال بالا (مثال اول) نمی تواند برای بازگشت انتهایی بهینه شود. در اینجا یک برنامه متفاوت برای انجام همان کار وجود دارد.

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 modifier استفاده کرده ایم که به کامپایلر می گوید بازگشت را بهینه کند.

منبع.

لیست جلسات قبل آموزش برنامه نویسی کاتلین

1. معرفی کاتلین،  Kotlin Hello World – اولین برنامه کاتلین
2. انواع متغیرهای پایه در کاتلین
3. عملگرهای برنامه نویسی کاتلین
4. تبدیل نوع در برنامه نویسی کاتلین
5. عبارت ها، گزاره ها و بلوک ها در برنامه نویسی کاتلین
6. کامنت ها در برنامه نویسی کاتلین
7. ورودی / خروجی پایه در برنامه نویسی کاتلین
8. عبارت if در برنامه نویسی کاتلین
9. عبارت when در برنامه نویسی کاتلین
10. حلقه های while و do … while در برنامه نویسی کاتلین
11. حلقه for در برنامه نویسی کاتلین
12. عبارت break در برنامه نویسی کاتلین
13. عبارت continue در برنامه نویسی کاتلین
14. توابع در برنامه نویسی کاتلین
15. فراخوانی تابع میانوندی در برنامه نویسی کاتلین
16. آرگومان ‌های پیش ‌فرضآرگومان ‌های پیش ‌فرض و نام ‌دار در برنامه نویسی کاتلین